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

solution:

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // slow is end of first part of list
        ListNode sndHead = reverse(slow.next);
        slow.next = null;
        while (sndHead != null) {
            ListNode headNext = head.next;
            head.next = sndHead;
            ListNode sndHeadNext = sndHead.next;
            sndHead.next = headNext;
            head = headNext;
            sndHead = sndHeadNext;
        }
        
    }
    private ListNode reverse(ListNode node) {
        // reverse linked list from node to the end, return the new head
        ListNode prev = null, next = null, current = node;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }
}

3 steps:

  1. find the middle point which seperates the list into two parts
  2. reverse the 2nd part of list
  3. “stich” two parts of list together one by one.

What I did wrong: (After thought)

I can’t find the ending condition for the while loop below, since we are stiching the two list together, we need to find the list which is shorter, in other word: which exhaust first. Otherwise, null pointer everywhere.

1
2
3
4
5
6
7
8
while (sndHead != null) {
            ListNode headNext = head.next;
            head.next = sndHead;
            ListNode sndHeadNext = sndHead.next;
            sndHead.next = headNext;
            head = headNext;
            sndHead = sndHeadNext;
        }