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/
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;
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