题目描述

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Given 1->2->3->4, reorder it to 1->4->2->3.
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

题意：将一个链表的第$k$项和倒数第$k$项放在一起。

算法1

(暴力枚举) $O(n^2)$

题解1:暴力解法，每次找到链表末尾节点插入到原来第$k$个节点后面。时间复杂度$O(n^2)$

C++ 代码

    void reorderList(ListNode* head) {
        if(!head || !head->next || !head->next->next)return ;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        //head是第k个节点的位置
        while(head->next && head->next->next)
        {
            ListNode* tail = head;
            //找到末尾节点的前驱节点，同时将末尾节点插入到head后面
            while(tail->next->next) tail = tail->next;
            tail->next->next = head->next;
            head->next = tail->next;
            //更新tail和head
            tail->next = NULL;
            head = head->next->next;
        }
    }

算法2

题解2:我们可以先把链表的后半部分反转过来，然后就可以从两端开始遍历，将末尾节点插入第$k$个节点后面。时间复杂度：查找中间节点$O(n)$，反转后半部分链表$O(n)$，依次插入后半部分的节点$O(n)$，总的时间复杂度为$O(n)$。

C++ 代码

   void reorderList(ListNode* head) {
        if(!head || !head->next || !head->next->next) return;
        ListNode* slow = head;
        ListNode* quick = head;
        //找到中间节点（如果有两个中间节点,slow是靠后的那个）
        while(quick && quick->next)
        {
            slow = slow->next;
            quick = quick->next->next;
        }
        //反转slow后面的所有节点
        ListNode* pre = slow;
        ListNode* cur = slow->next;
        slow->next = NULL;
        while(cur)
        {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            if(temp == NULL)
                break;
            cur = temp;
        }
        //此时cur是最后一个节点。跳出循环有两种情况：
        //总共有偶数个节点，最后两个节点就不用反转了；head->next != cur
        //总共有奇数个节点，最后一个节点不用反转。head!= cur
        while(head->next != cur && head!= cur)
        {
            ListNode* temp = cur->next;
            cur->next = head->next;
            head->next = cur;
            cur = temp;
            head = head->next->next;
        }
    }