Problem description:

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.

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.

Solution:

The idea is to divide the list into two half. Reverse the second half, then reassemble the list.

example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

cut the list into half
1-2-3-4-5-6
    |     |
   slow  fast


reverse the second part of the list
1-2-3-4-5-6
    | |    
   mid|  
     pre


1-2-3-4-5-6   original

      4
1-2-3/  > 6   make 4 point to tmp->next, which is 6
      5

1-2-3 5-4-6   make 5->next point to 4
1-2-3-5-4-6   make mid->next point to 5

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
size, p = 1, head
while p:
    p, size = p.next, size+1

p = head
for _ in range(size//2 - 1):
    p = p.next
q = p.next
p.next = None


#reverse next half
half, half.next = ListNode(0), q

while q and q.next:
    tmp = half.next
    half.next = q.next
    q.next = q.next.next
    half.next.next = tmp

p, q = head, half.next
while p and q:
    p2, q2 = p.next, q.next
    p.next = q
    q.next = p2
    p = p2
    q = q2
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
/**
 * 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 == NULL || head->next == NULL) return;
        
        ListNode *slow= head, *fast= head;
        while(fast->next && fast->next->next){ 
            slow = slow->next;
            fast = fast->next->next;
        }
        
        ListNode* middle = slow;
        ListNode* preCurrent = slow->next;
        while(preCurrent->next != NULL){ //use preCurrent->next to determine whether if there's more element need to reverse
            
            ListNode *tmp = preCurrent->next; 
            preCurrent->next = tmp->next;
            tmp->next = middle->next;
            middle->next= tmp;
        }
        
        slow = head; //first part of the list
        fast = middle->next; //second part of the list
        while(slow != middle){
            middle->next = fast->next;
            fast->next= slow->next;
            slow->next= fast;
            slow= fast->next;
            fast= middle->next;
        }
    }
};

time complexity: $O(n)$
space complexity: $O(1)$

Solution 2

Another way is to use stack to keep all the second half nodes. Since stack is last in first out, we would get the last node when we rearrange the list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
stk = collections.deque()
size, p = 1, head
while p:
    p, size = p.next, size+1

p = head
for _ in range(size // 2 - 1):
    p = p.next

q = p.next # head of second half list
p.next = None # let first half end

while q:
    stk.append(q)
    q = q.next

p = head
while stk and p:
    top = stk.pop()
    top.next = p.next
    p.next = top
    p = p.next.next

time complexity: $O(n)$
space complexity: $O(1)$

reference:
https://goo.gl/5MyHcY