Reverse 2nd half & merge with visual aids and readable code


  • 0
    T
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return; // [] and [x]
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) { // stop before reaching end
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast.next != null) fast = fast.next; // in case count is odd
        // Partitions of equal length (first half may be 1 longer):
        // [head ... slow | slow.next ... fast]
        ListNode half1 = head;
        ListNode half2 = slow.next;
    
        half2 = reverse(half2);
        slow.next = null; // cut first half from second half
        // [head ... slow] + [fast ... slow.next]
        merge(half1, half2);
    }
    
    ListNode reverse(ListNode head) {
        ListNode tail = head;
        while (tail.next != null) {
        	// save pointers
            ListNode next = tail.next;
            ListNode rest = next.next;
    
            //    [head ... tail next rest]
            // -> [next head ... tail rest]
            tail.next = rest;
            next.next = head;
    
            // advance forward
            head = next;
        }
        return head;
    }
    
    ListNode merge(ListNode head, ListNode other) {
        ListNode node1 = head, node2 = other;
        while (node1 != null && node2 != null) {
            // save pointers
            ListNode next1 = node1.next;
            ListNode next2 = node2.next;
            
            //    [head ... node1 next1 list1] + [node2 next2 list2]
            // -> [head ... node1 node2 next1 list1] + [next2 list2]
            node1.next = node2;
            node2.next = next1;
    
            // advance forward
            node1 = next1;
            node2 = next2;
        }
        return head;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.