Reorder list

Input: head = [1,2,3,4] Output: [1,4,2,3]

First find the middle of the list Second reverse the second half Third merge the two lists

1. Find the middle of the list by using the fast pointer/slow pointer technique.

   //given ListNode head
   ListNode fast = head;
   ListNode slow = head;
   while(fast != null && fast.next !=null){
    fast = fast.next.next;
    slow = slow.next;
   }
   

2. Reverse the second list.

   ListNode prev= null;
   ListNode curr = slow;
   ListNode temp;
   while(curr != null){
    temp = curr.next;
    curr.next = prev;
   
    curr = temp;
    prev = curr;
   }
   

1. Merge the two lists. Remember to point twice first

   second = prev;
   ListNode first = head;
   while(second.next != null){
    temp = first.next 
    first.next = second;
    first = temp;
   
    temp = second.next;
    second.next = first;
    second = temp;
   }
   

Trick: assign temp to next, point next to destination. Z pattern. Temporary variables.