143.Reorder List¶

143.Reorder List¶

Tags: Medium Linked List

Links: https://leetcode.com/problems/reorder-list/

Given a singly linked list L: L*0→*L*1→…→*L**n-1→L*n, reorder it to: *L*0→*L**n→L*1→*L**n-1→L*2→*L**n-2→…

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

Example 1:

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

Example 2:

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

最直接的思路，类似于删除倒数第k个数，先找出要插入的部分，注意要插入的部分是倒过来的，所以中间需要一步翻转链表。翻转完成之后就是两个链表的合并了。思路很直接，但是速度很不理想。

Runtime: 784 ms, faster than 6.00% of C++ online submissions for Reorder List.
Memory Usage: 12.2 MB, less than 82.35% of C++ online submissions for Reorder List.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        //空链表或链表只有一个或两个元素节点
        if (!head || !head -> next || !head -> next -> next) return;

        //保证了链表里至少三个节点
        ListNode * dummy1 = new ListNode(0);
        dummy1 -> next = head;

        int cnt = 0; //记录链表长度
        ListNode * cur = dummy1, *pre = dummy1;
        while(cur -> next){
            ++cnt;
            cur = cur -> next;
        }

        int half = 0;//需要插入的链表长度
        if (cnt % 2 == 0) half = cnt / 2 - 1;
        else half = cnt / 2; 

        cur = head;
        ListNode *prob = cur;
        do{
            for (int i = 1; i <= half - 1; ++i)
                prob = prob -> next;

            if (!prob -> next) break;
            cur = cur -> next;
            pre = pre -> next;
            prob = cur;
        } while(true);

        //把原来的链断开
        pre -> next = nullptr;
        //尾部的链需要翻转
        ListNode * dummy2 = new ListNode(0);
        dummy2 -> next = cur;
        pre = cur;
        cur = cur -> next;
        while(cur) {
            pre -> next = cur -> next;
            cur -> next = dummy2 -> next;
            dummy2 -> next = cur;
            cur = pre -> next;
        }

        //两个链合并
        pre = head;
        cur = pre -> next;
        prob = dummy2 -> next;
        while (dummy2 -> next) {
            dummy2 -> next = prob -> next;
            prob -> next = cur;
            pre -> next = prob;
            pre = pre -> next -> next;
            cur = pre -> next;
            prob = dummy2 -> next;
        }
    }
};

速度慢的原因根本在于查找断开的位置部分，如果链表很长，那么就需要反复探测。所以改进的方案就是快慢指针，很明显我们需要在中间断开，利用快慢指针就不用再考虑长度是奇数还是偶数了。

改进后的方案：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        //空链表或链表只有一个或两个元素节点
        if (!head || !head -> next || !head -> next -> next) return;

        //保证了链表里至少三个节点
        ListNode * dummy1 = new ListNode(0);
        dummy1 -> next = head;

        //快慢指针从中间断开
        ListNode *pre = head, *cur = head;
        while (cur && cur -> next) {
            pre = pre -> next;
            cur = cur -> next -> next;
        }

        //把原来的链断开
        cur = pre -> next;
        pre -> next = nullptr;
        //尾部的链需要翻转
        ListNode * dummy2 = new ListNode(0);
        dummy2 -> next = cur;
        pre = cur;
        cur = cur -> next;
        while(cur) {
            pre -> next = cur -> next;
            cur -> next = dummy2 -> next;
            dummy2 -> next = cur;
            cur = pre -> next;
        }

        //两个链合并
        pre = head;
        cur = pre -> next;
        ListNode * prob = dummy2 -> next;
        while (dummy2 -> next) {
            dummy2 -> next = prob -> next;
            prob -> next = cur;
            pre -> next = prob;
            pre = pre -> next -> next;
            cur = pre -> next;
            prob = dummy2 -> next;
        }
    }
};

速度明显加快了！

Runtime: 48 ms, faster than 78.36% of C++ online submissions for Reorder List.
Memory Usage: 12 MB, less than 100.00% of C++ online submissions for Reorder List.