143. Reorder List

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.

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

My Solutions:

• 分三步：

  • 找到后半部分 (findMiddle)

  • 反转后半部分 (reverse)

  • 把前后连起来 (merge)

• Time: O(n); Space: O(1)

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;
        
        
        //1. find middle point of linked list
        ListNode middle = findMiddle(head);
        
        
        //2. reverse the 2nd half; change the tail of 1st half to null
        ListNode head2 = reverse(middle.next);
        middle.next = null;
        
        //3. combine 1st and 2nd half
        ListNode head1 = head;
        merge(head1, head2);
        
     }
    
    private ListNode findMiddle(ListNode head) {
        if (head == null) return null;
        ListNode slow = head, fast = head; 
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
    
    private void merge(ListNode n1, ListNode n2) {
        while (n2 != null) {
            ListNode temp1 = n1.next;
            ListNode temp2 = n2.next;
            
            n1.next = n2;
            if (temp1 == null) break;
            n2.next = temp1;
            n1 = temp1;
            n2 = temp2;
        }
    }
}