143.重排链表

143.重排链表

#链表 2024-08-07

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* left = head;
        ListNode* right = head->next;
        while (right) {
            ListNode* node = right->next;
            right->next = left;
            left = right;
            right = node;
        }
        head->next = nullptr;
        return left;
    }

    void reorderList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return;
        }
        // 找到中间节点进行切割，左半部分链表保持不变，反转右半部分链表
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* left = head;
        ListNode* right = slow->next;
        slow->next = nullptr;
        right = reverseList(right);

        // 准备工作已做好，开始重排
        ListNode* virtualHead = new ListNode(-1);
        ListNode* tmp = virtualHead;
        while (left != nullptr && right != nullptr) {
            tmp->next = left;
            left = left->next;
            tmp->next->next = right;
            right = right->next;
            tmp = tmp->next->next;
        }

        if (left != nullptr) {
            tmp->next = left;
        }

        head = virtualHead->next;
    }
};

这道题只要能够把题目看明白，即它究竟是如何重排，逻辑上理清楚并不难

1. 先找到中间节点，将当前链表分割成两部分，即左链表和右链表
2. 左链表的尾节点要指向 nullptr，右链表需要反转
3. 创建一个虚拟头节点用来链接后续重排的节点，先链接左链表的第一个节点，接着链接右链表的第一个节点，如此循环
4. 如果左链表当前节点和右链表当前节点有一个不满足不为空就退出循环。由于左链表的长度大于或等于右链表（如果大于，也只会比其多一个节点），退出循环之后，继续判断左链表当前节点是否为空，不为空就代表还有一个节点被遗漏，tmp 指向这个节点即可
5. 最后，记得更换 head 节点为 virtualHead->next

---

完成本题的过程中，犯下的错误是 tmp 节点的移动，错误的逻辑代码如下：

while (left != nullptr && right != nullptr) {
  tmp->next = left;
  tmp = tmp->next;		// 错误的逻辑代码，后续代码也没价值
  tmp->next = right;
  tmp = tmp->next;		
  left = left->next;
  right = right->next;
}

因为我们的 left 和 right 节点后面也跟着很多的节点，如果你 tmp = tmp->next，然后再 tmp->next = right，就失去 left 链表的掌控了（left 链表被污染），从而出现错误。

所以，只需要每次让 tmp 指向 left 或 right 的节点之后，及时更新 left 和 right 指针即可，保证不被污染

while (left != nullptr && right != nullptr) {
     tmp->next = left;
     left = left->next;
     tmp->next->next = right;
     right = right->next;
     tmp = tmp->next->next;
 }