Leetcode -- 143. Reorder List(LinkedList)

143. Reorder List
medium
https://leetcode.com/problems/reorder-list/#/description

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-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;
    }