Reorder List Leetcode


#1

Given a singly linked list L: L0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

#2

The code splits the list in the middle, reverses the second half and merges the code.

class Solution {
    public void reorderList(ListNode head) {
        if(head==null) return;
        
        // identify mid
        ListNode slow = head, fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // reverse second part
        ListNode head2 = reverse(slow.next);
        slow.next = null;
        
        // merge both lists
        merge(head, head2);
    }
    
    // 4->5 to 5->4. new head will be 5
    private ListNode reverse(ListNode cur){
        ListNode prev = null, next = null;
        while(cur!=null){
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    
    // 1->2->3 and 5->4 or 1->2 and 4->3 etc
    private void merge(ListNode head, ListNode head2){
        while(head!=null && head2!=null){
            ListNode t1 = head.next;
            ListNode t2 = head2.next;
            head2.next = head.next;
            head.next = head2;
            head = t1; head2 = t2;
        }
    }

}