1
class Solution {
2
  public void reorderList(ListNode head) {
3
    if (head == null) return;
4

5
    // Find start of second list
6
    ListNode slow = head, fast = head;
7
    while (fast != null && fast.next != null) {
8
      slow = slow.next;
9
      fast = fast.next.next;
10
    }
11

12
    ListNode list1 = head;
13
    ListNode list2 = reverseList(slow.next); // slow.next is start of list2
14

15
    // Break first list from second list!
16
    slow.next = null;
17

18
    // Merge list1 and list2
19
    while (list2 != null) {
20
      ListNode l1Next = list1.next;
21
      ListNode l2Next = list2.next;
22
      list2.next = list1.next;
23
      list1.next = list2;
24
      list1 = l1Next;
25
      list2 = l2Next;
26
    }
27
  }
28

29
  private ListNode reverseList(ListNode node) {
30
    if (node == null) return node;
31
    ListNode newHead = null, currNode = node;
32
    while (currNode != null) {
33
      ListNode backup = currNode.next;
34
      currNode.next = newHead;
35
      newHead = currNode;
36
      currNode = backup;
37
    }
38
    return newHead;
39
  }
40
}