Question
Formatted question description: https://leetcode.ca/all/143.html

```
143 Reorder List
Given a singly linked list L: L0 → L1 → … → Ln-1 → Ln,
reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 →…
You must do this in-place without altering the nodes' values.
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.
@tag-linkedlist
```

Algorithm
Divided into the following three small questions:

Use the fast/slow pointers to find the midpoint of the linked list and disconnect the linked list from the midpoint to form two independent linked lists.
Reverse the second half of list.
Insert the elements of the second half linked list into the first linked list.
Code
Java

import java.util.Stack ;
public class Reorder_List {
/**
* 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 || head . next == null ) return ;
ListNode dummy = new ListNode ( 0 );
dummy . next = head ;
ListNode prev = dummy ;
ListNode fast = head , slow = head ;
// step-1, find mid
while ( fast != null && fast . next != null ) {
fast = fast . next . next ;
prev = slow ;
slow = slow . next ;
}
// 1,2,3 prev->1, slow->2
// 1,2,3,4 prev->2, slow->3
// that is, left is always smaller or equal to right
ListNode right = prev . next ; // not using slow, because for case list [1]. update: no, must tive single node special check
prev . next = null ; // @note:@memorize: cut
// step-2, reverse 2nd half
ListNode rightReversed = reverse ( right );
// step-3, merge
ListNode p = head ;
while ( p != null || rightReversed != null ) {
if ( p . next == null ) { // left: [1], right [2,3], directly append
p . next = rightReversed ;
break ;
}
else {
// record second of both left/right list
ListNode oldLeftNext = p . next ;
// p.next = new ListNode(rightReversed.val);// this is one way, but not in place...
// p.next.next = oldLeftNext;
ListNode oldRightNext = rightReversed . next ;
// linked two heads from left and right
p . next = rightReversed ;
rightReversed . next = oldLeftNext ;
// update
p = oldLeftNext ;
rightReversed = oldRightNext ;
}
}
head = dummy . next ;
}
public ListNode reverse ( ListNode head ) {
ListNode dummy = new ListNode ( 0 );
dummy . next = head ;
while ( head . next != null ) {
ListNode newhead = head . next ;
ListNode current = dummy . next ;
dummy . next = newhead ;
head . next = newhead . next ;
newhead . next = current ;
}
return dummy . next ;
}
}
public class Solution_stack {
public void reorderList ( ListNode head ) {
// @note: my idea is, find mid point, then 2nd half put in a stack to reverse the order I get the 2nd half nodes
// eg: [1,2,3,4], in stack is 4->3, then 1, sk.pop=4, 2, sk.pop=3
if ( head == null || head . next == null || head . next . next == null ) { // if single node list, then return
return ;
}
ListNode dummy = new ListNode ( 0 );
dummy . next = head ;
ListNode prev = dummy ;
// fast-slow pointers to find mid of list
ListNode fast = head ;
ListNode slow = head ;
while ( fast != null && fast . next != null ) { // no need check slow, since fast is reaching end first
prev = slow ;
slow = slow . next ;
fast = fast . next . next ;
}
// now slow is at mid, prev at mid-1
// from mid to end, push to stack
Stack < ListNode > sk = new Stack <>();
ListNode mid = slow ;
while ( slow != null ) {
sk . push ( slow );
// System.out.println("push to stack: " + slow.val);
slow = slow . next ;
}
// start reorder
ListNode tail = head ; // @note: if only one node as head, then head is in stack
while (! sk . isEmpty () && tail != mid ) { // @note: if tail is already mid node, then done
ListNode originalNext = tail . next ;
tail . next = sk . pop ();
tail = tail . next ; // now tail is the one from 2nd half
if ( tail == mid ) {
break ;
}
tail . next = originalNext ;
tail = tail . next ; // now tail is next of left-half current node
}
// @note:@memorize: very important, avoid infinite self-looping
tail . next = null ;
return ;
}
}
}