143. Reorder List

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        // devide the list into two half
        // corner case will be included
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null && fast.next.next != null){
            slow=slow.next;
            fast = fast.next.next;
        }
        
        // slow will never be null, unless if head is null
        // reverse the second part of the list
        ListNode first = null;
        ListNode second = slow.next;
        while(second!=null){
            ListNode temp = second.next;
            second.next= first;
            first = second;
            second = temp;
        }
        
        
        // separate the list from the middle
        slow.next = null;
        
        ListNode one = head;
        ListNode two = first;
        while(one!=null && two !=null){
            ListNode temp=two.next;
            two.next=one.next;
            one.next=two;
            one = two.next;
            two = temp;
        }
    }
}