Algorithm

LintCode/Reorder List

Problem Summary

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] -> …

Solution

First, we find the middle node of list L.
We can use two pointers, fast and slow, both initialized with head pointer of list L, to find the middle node in one-pass. Every time the slow pointer moves one step, the fast pointer moves two step. So when the fast pointer or its next reaches the end, the slow pointer is at the middle node.

Second, we cut list L into two halves, L1 and L2. L1 ends at the middle node and L2 starts at the next node of the middle node. Then we reverse L2, and we use L3 to denote the reversed list.

Third, we merge L1 and L3.

The time and space complexities are O(N) and O(1), respectively.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    /*
     * @param head: The head of linked list.
     * @return: nothing
     */
    ListNode* reverse_list(ListNode * head)
    {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode *p = head, *q = head->next, *tmp;
        while (p && q)
        {
            tmp = q->next;
            q->next = p;
            p = q;
            q = tmp;
        }
        head->next = NULL;
        return p;
    }
    void reorderList(ListNode * head) {
        if (head == NULL)
            return;
        ListNode *fast = head,*slow = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *latter = slow->next;
        slow->next = NULL;
        latter = reverse_list(latter);
        fast = head;
        ListNode *tmp1,*tmp2;
        while (fast && latter)
        {
            tmp1 = fast->next;
            fast->next = latter;
            tmp2 = latter->next;
            fast = latter->next = tmp1;
            latter = tmp2;
        }
    }
};