LCR 026. 重排链表 - 力扣（LeetCode）

题目要求：

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

 L0 → L1 → … → Ln-1 → Ln 
请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

输入: head = [1,2,3,4]
输出: [1,4,2,3]

示例 2:

输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]

提示：

• 链表的长度范围为 [1, 5 * 10^4]
• 1 <= node.val <= 1000

双指针 O(N)：

        将每个节点的指针以此保持在一个数组中，按照一左一右的顺序依次连接即可。

class Solution {
public:void reorderList(ListNode* head) {int n = 0;ListNode* tail = head;vector<ListNode*> Nodes(50000);while (tail) {Nodes[n++] = tail;tail = tail->next;}int left = 0, right = n - 1;ListNode* phead = new ListNode(); // 哨兵位ListNode* cur = phead;while (left <= right) {cur->next = Nodes[left++];cur = cur->next;cur->next = Nodes[right--];cur = cur->next;}cur->next = nullptr;head = phead->next;}
};