Data Structures & Algorithms in Java – Linked List – Reorder List

Problem:

Given a singly linked list , reorder it in such a way that the first and last elements are next to each other , the second and second from last are next to each other etc.

For example,

Given the list [1,2,3,4,5]

Reorder it into:

[1,5,2,4,3]

As you see we are merging elements from the first and last together until the list is exhaused.

Try out the solution here:

https://leetcode.com/problems/reorder-list/solution/

Advertisements

Solution:

Hint:

The solution to this problem involves three major steps:

  • Find the middle of the linked list
  • Reverse the second half of the linked list
  • Merge the first half and the second half

Explanation:

The steps given in the hint are separate problems themselves and we have already looked into the second and third here:

For finding the middle of the linked list , you maintain two pointers , a slow one and a fast one similar to the ones used to detect a cycle in a linked list.

Both the pointers point to the head element initially and then you increment slow pointer by one node and fast pointer by two nodes. By the time fast pointer reaches the end of the list slow pointer would be pointing to the beginning of the second half.

Here is the code for the same:

       
     
        ListNode slow = head;
        
        ListNode fast = head;
        

        while(fast!=null && fast.next!=null){
            
            slow = slow.next;
            
            fast = fast.next.next;
        }

The second step is to reverse the later half.

That can be done by the below code:

    
    public ListNode reverse(ListNode head){
        
    
        ListNode newNode = null;
        
        
        while(head != null){
            
            ListNode next = head.next;
            
            head.next = newNode;
            
            newNode = head;
            
            head = next;
               
        }
          
        return newNode;
    }

Finally you merge the first half and second half using the below code:

You stop merging when the first half and second don’t collide.

You pick one from each half and keep adding them to a tail node as shown below:

     ListNode resultHead = new ListNode();
        
        ListNode resultTail = resultHead;
        
        ListNode first = head;

        
        while(first != null && slow != null && first != slow){
            
            
            
            resultTail.next = first;
            
            first = first.next;
            
            resultTail = resultTail.next;
            
            resultTail.next = slow;
            
            slow = slow.next;
            
            
            
            resultTail = resultTail.next;
            
            
        }
        
        head = resultHead.next;
Advertisements

ALGORITHM:

STEP 1: Initialize two pointers slow and fast

STEP 2: Move slow pointer by one node and fast pointer by two nodes until you reach the end of the list.

STEP 3: The slow pointer now points to the first element of the second half. Using this as head node reverse the second half

STEP 4: Merge the reversed half and the first half (use a pointer to point to the head and use it as the head of the first half)

Here is the full code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        
        
        
     
        ListNode slow = head;
        
        ListNode fast = head;
        
       //find middle 
        while(fast!=null && fast.next!=null){
            
            slow = slow.next;
            
            fast = fast.next.next;
        }
        
     //reverse later half 
      slow =  reverse(slow);
       

        
        //merge them
        ListNode resultHead = new ListNode();
        
        ListNode resultTail = resultHead;
        
        ListNode first = head;

        
        while(first != null && slow != null && first != slow){
            
            
            
            resultTail.next = first;
            
            first = first.next;
            
            resultTail = resultTail.next;
            
            resultTail.next = slow;
            
            slow = slow.next;
            
            
            
            resultTail = resultTail.next;
            
            
        }
        
        head = resultHead.next;
        

    
   
        
        
        
        
    
        
    
        
        
    }
    
    
    public ListNode reverse(ListNode head){
        
    
        ListNode newNode = null;
        
        
        while(head != null){
            
            ListNode next = head.next;
            
            head.next = newNode;
            
            newNode = head;
            
            head = next;
            
            
            
            
        }
        
        
        
        return newNode;
    }
}

Time complexity of finding the middle element is O(n) , reversing the second half is O(n/2) and merging the two lists is O(n/2).

So total time complexity is O(n)

Space complexity is O(1) since we don’t use any space in proportion to the input. Just a few nodes used as pointers.

That’s it!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s