Given a linked list L: L0→L1→…→Ln-1→Ln , can you reorder it to L0→Ln→L1→Ln-1→L2→Ln-2→…?

For example,

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

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

Before we get into the details, let's look at our solution here:

    public void reorderList(ListNode head) {
    
        if(head == null){
            return;
        }
        
        ListNode slow = head, fast = head;

        // 1. get the middle node
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;   
        }
        
        // get the head of second list
        ListNode newHead = slow.next;
        
        // break the first list
        slow.next = null;
        
        // 2. reverse the second half list
        ListNode prev = null;
        while(newHead != null){      
            ListNode temp = newHead.next;
            newHead.next = prev;
            prev = newHead;
            newHead = temp; 
        }
    
        // 3. merge two lists     
        ListNode dummy = new ListNode(0);
        boolean isOdd = true;
        while(head != null && prev != null){
            
            if(isOdd){
                dummy.next = head;
                head = head.next;
            } else{
                dummy.next = prev;
                prev = prev.next;
            }
            dummy = dummy.next;
            isOdd = !isOdd;
        }
        
        if(head != null){
            dummy.next = head;
        } else{
            dummy.next = prev;
        }   
    }

You can break the solution into 3 parts:

1. find the middle node using slow and fast node
2. reverse the second half list
3. merge two lists

---

You might a question daunting just because it is long or hard to understand. Often times, the best thing you can do is to break down the question into several parts, and soon you will realize that it is not as hard as you think it would be. Hope this post helps! See you later!

Post was published on 1 Feb 2020, last updated on 1 Feb 2020.

Like the content? Support the author by paypal.me!