143. Reorder List

143. Reorder List (Medium)

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→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.

Companies:
Facebook, Microsoft, Google

Related Topics:
Linked List

Solution 1.

// OJ: https://leetcode.com/problems/reorder-list/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
private:
    ListNode *reverse(ListNode* head) {
        ListNode dummy;
        while (head) {
            auto node = head;
            head = head->next;
            node->next = dummy.next;
            dummy.next = node;
        }
        return dummy.next;
    }
    int getLength(ListNode *head) {
        int len = 0;
        for (; head; head = head->next) ++len;
        return len;
    }
public:
    void reorderList(ListNode* head) {
        if (!head) return;
        int len = (getLength(head) - 1) / 2;
        ListNode *p = head, *q;
        while (len--) p = p->next;
        q = p->next;
        p->next = NULL;
        q = reverse(q);
        p = head;
        while (q) {
            auto node = q;
            q = q->next;
            node->next = p->next;
            p->next = node;
            p = node->next;
        }
    }
};

Solution 2

// OJ: https://leetcode.com/problems/reorder-list/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
private:
    ListNode *reverseList(ListNode *head) {
        ListNode newHead;
        while (head) {
            auto p = head;
            head = head->next;
            p->next = newHead.next;
            newHead.next = p;
        }
        return newHead.next;
    }
public:
    void reorderList(ListNode* head) {
        if (!head) return;
        ListNode *fast = head, *slow = head, *rightHead;
        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        rightHead = slow->next;
        slow->next = NULL;
        rightHead = reverseList(rightHead);
        while (rightHead) {
            auto p = rightHead;
            rightHead = rightHead->next;
            p->next = head->next;
            head->next = p;
            head = p->next;
        }
    }
};