LeetCode 143 - Reorder List

http://rainykat.blogspot.com/2017/03/leetcode-143-reorder-listlinkedlist.html
https://leetcode.com/problems/reorder-list/#/description

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.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

思路： Three steps
           1. Find the middle of list
           2. Reverse the last half o list (from the next one of middle)
           3. Connect 1st half and 2nd half iteratively 

Complexity: Time O(n) Space O(1)

public void reorderList(ListNode head) {
        if(head == null)return;
        ListNode slow = head;
        ListNode fast = head;
        
        //1. find the middle of list
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode tmp = slow.next;//2nd half start from next node of the middle one
        slow.next = null;
        
        //2. reverse last half of list
        ListNode newHead = reverseList(tmp);
        
        //3. connect 1st half to 2nd half
        ListNode cur = head;
        while(cur != null && newHead != null){
            ListNode tmp1 = cur.next;
            ListNode tmp2 = newHead.next;
            cur.next = newHead;
            newHead.next = tmp1;
            cur = tmp1;
            newHead = tmp2;
        }
    }
    
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){ return head;}
        ListNode nextN = head.next;
        head.next = null;
        while(nextN != null){
            ListNode tmp = nextN.next;
            nextN.next = head;
            head = nextN;
            nextN = tmp;
        }
        return head;
    }