143.Reorder List | LEETCODE MEDIUM |
Qns Link: https://leetcode.com/problems/reorder-list/description/
Hello everyone, let's tackle another Leetcode problem that involves linked lists. If you're preparing for a technical interview or an online assessment, chances are high that your interviewer will ask you this question, as it is quite an interesting one. This problem has been asked in several tech giants, including Amazon. In our previous articles, we've discussed various approaches such as two pointers, merging lists, and reversing lists in linked lists. I highly recommend that you read those articles, as they will undoubtedly assist you in acing your coding interviews.
Prerequisites: Our article on reversing linked list patterns, two pointers.
If you are reading my article on problem-solving, you will notice that we always begin by outlining the thought process, rather than immediately diving into the solution.
Let’s see what they asked to do,
We are given the list and you have to reorder the list based on the given condition.
Given : L0 → L1 → … → Ln — 1 → Ln
After reorder: L0 → Ln → L1 → Ln — 1 → L2 → Ln — 2 → …
This problem is just an implementation problem, to tackle implementation problems, it is helpful to take a pen and paper and draw out the given linked list along with the required list based on the given condition. This helps to organize your thoughts and approach the problem systematically. By doing so, you can efficiently transform the given list into the required list.
If you are familiar with the concepts of finding the middle node and reversing the list, then this problem will be very easy for you. If you are not aware of these concepts, please refer to my articles on finding the middle node and reversing the list.
To achieve the desired output, we simply need to reverse from the middle node and obtain two lists. Then, we can merge these two lists - one from the first list and the other from the second list. By following these simple steps, we can successfully obtain the desired output. It's a simple and easy process.
Let’s check our thoughts with the example given in the leetcode,
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
In the given input the middle node is 3, reverse the list from 3. Now we have two lists i.e
1st list : 1 →2 →3 →NULL
2nd list : 5 →4 →3 →NULL
Now, we need to merge the elements from both lists until both lists don't point to NULL. The resulting list will be 1 → 5 → 2 → 4 → 3 → NULL.
Now we know what to do, this is the thought process behind brainstorming this problem.
Now it is time to see how to do,
👊Check the edge cases i.e. check if the list is null or if it contains only one element, if so just return the the list.
if(head==null || head.next==null){
return;
}👊Find the middle node with help of the Floyd’s Algorithm which I clearly explained in my article on two-pointers (LINK). Let’s see a gist of Floyd’s Algorithm(fast and slow pointer), just move the fast pointer twice the faster than the slow pointer until the fast pointer becomes null and finally return the slow pointer since now the slow pointer points to the middle node.
public ListNode reverseList(ListNode head) {
ListNode prev=null;
ListNode present=head;
while(present!=null){
ListNode next=present.next;
present.next=prev;
prev=present;
present=next;
if(next!=null){
next=next.next;}
}
return prev;
}👊Now start reversing the list from the middle node that we found. If you find it difficult to reverse the list then I recommend you to read my article on reversing the list(LINK). Let’s see a gist of the reversing list, using three pointers as previous, current, and next. Initially, they point to,
previous=NULL, current=head(1st node), and next=node next to the current node.
Connect the current to the previous node move other nodes accordingly until the current points to NULL and finally return the previous pointer.
public ListNode reverseList(ListNode head) {
ListNode prev=null;
ListNode present=head;
while(present!=null){
ListNode next=present.next;
present.next=prev;
prev=present;
present=next;
if(next!=null){
next=next.next;}
}
return prev;
}👊Now we have two lists, one is the given list another is reversed list. Merge them alternatively for the resultant list.
Let the head of the given list is stored in a variable hf(headfirst) and the head of the reversed list is stored in a variable hs(headSecond).
1st list : 1 →2 →3 →NULL
2nd list : 5 →4 →3 →NULL
In our case hf points to 1 and hs points to 5. Now start merging alternatively between the 2 lists until the element of any list points to NULL.
1st step: In the first step our motive is to connect 1 to 5 so store the node which is pointed by the hf (in our case it is 2) in variable temp which helps to move the hs in the next iteration. Then make the hf to point hs. Now we got 1 → 5.
Now move the hf to the next node of the node which it points initially(i.e. now hf is 2) with the help of the temp variable which we used in our previous process.
2nd step: Our next intent is to connect 5 to 2 so store the node pointed by the hs (in our case it is 4) in variable temp which helps to move the hs in the next iteration. Then make the hs to point hf (in our case hs is 5 and hf is 2). Now the resultant list is 1 → 5 → 2.
Now move the hs to the next node of the node which it points initially(i.e. now hs is 4) with the help of the temp variable which we used in our previous process.
We repeat these steps until any of the lists points to null. Finally, we check if hf is not null, and if so, make it point to null.
Following this process, we can obtain the output of [1,5,2,4,3] given the input of [1,2,3,4,5]. If you need more information on certain steps, you can refer to my articles on reversing a list and the two-pointer technique.
/**
* 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 ListNode reverseList(ListNode head) {
ListNode prev=null;
ListNode present=head;
while(present!=null){
ListNode next=present.next;
present.next=prev;
prev=present;
present=next;
if(next!=null){
next=next.next;
}
}
return prev;
}
public ListNode middleNode(ListNode head) {
ListNode slow=head;
ListNode fast=head;
while(fast!=null && fast.next!=null){
slow=slow.next;
fast=fast.next.next;
}
return slow;
}
public void reorderList(ListNode head) {
if(head==null || head.next==null){
return;
}
ListNode mid=middleNode(head);
ListNode hs=reverseList(mid);
ListNode hf=head;
//rearrange
while(hf!=null && hs!=null){
ListNode temp=hf.next;
hf.next=hs;
hf=temp;
temp=hs.next;
hs.next=hf;
hs=temp;
}
//next of tail to null
if(hf!=null){
hf.next=null;
}
}
}Try the above program and get to understand the flow using the debug pointers.
If you find any value in this article, consider FOLLOWING me! Thanks 😇
#LearnInPublic #HappyCoding
