leetcode 链接：重排链表

题目

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

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

示例：

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

解答 & 代码

• 先定位到链表中间节点
• 再将链表右半部分反转，并将左半部分链表的末尾指向 nullptr
• 最后双指针同时遍历两部分链表，依次将右边的节点插入左边

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        // 特殊情况：如果链表节点数小于等于 2，不用重拍，直接返回
        if(head == nullptr || head->next == nullptr || head->next->next == nullptr)
            return;

        // 定位到链表中间节点
        ListNode* end = head->next;    // 尾节点
        ListNode* mid = head;        // 中间节点
        while(end != nullptr && end->next != nullptr)
        {    // end 每次走两步，mid 每次走一步，end 走到链表末尾，则 mid 指向链表中间节点
            mid = mid->next;
            end = end->next->next;
        }

        ListNode* leftEnd = mid;    // 链表左半部分的尾节点

        // 将链表右半部分反转
        ListNode* pre = nullptr;
        mid = mid->next;
        while(mid != nullptr)
        {
            ListNode* next = mid->next;
            mid->next = pre;
            pre = mid;
            mid = next;
        }
        ListNode* rightHead = pre;

        leftEnd->next = nullptr;    // 将链表左半部分的尾节点的 next 指向 nullptr

        // 双指针遍历左、右两边的链表，每次将右边的节点插入左边
        ListNode* cur1 = head;
        ListNode* cur2 = rightHead;
        while(cur2 != nullptr)
        {
            ListNode* next1 = cur1->next;
            ListNode* next2 = cur2->next;
            cur1->next = cur2;
            cur2->next = next1;
            cur1 = next1;
            cur2 = next2;
        }
    }
};

执行结果：

执行结果：通过

执行用时：48 ms, 在所有 C++ 提交中击败了 70.21% 的用户
内存消耗：17.4 MB, 在所有 C++ 提交中击败了 54.40% 的用户