Partition a list around a given point Geeks For Geeks
Problem Link:
https://practice.geeksforgeeks.org/problems/partition-a-linked-list-around-a-given-value/1
(It is also the problem of the day for 19-04-2022)
Solution 1: Without modification
class Solution {
public static Node partition(Node head, int x) {
Node temp=head;
Node temp1=new Node(-1);
Node temp2=new Node(-1);
Node temp3=new Node(-1);
Node temp4=temp1;
Node temp5=temp2;
Node temp6=temp3;
while(temp!=null){
if(temp.data<x){
temp1.next=new Node(temp.data);
temp=temp.next;
temp1=temp1.next;
}
else if(temp.data==x){
temp2.next=new Node(temp.data);
// temp2=temp2.next;
temp=temp.next;
temp2=temp2.next;
}
else{
temp3.next=new Node(temp.data);
// temp3=temp3.next;
temp=temp.next;
temp3=temp3.next;
}
}
Node temp41=temp4.next;
Node temp51=temp5.next;
Node temp61=temp6.next;
Node temp7= new Node(-1);
Node temp8=temp7;
while(temp41!=null){
temp7.next=new Node(temp41.data);
temp41=temp41.next;
temp7=temp7.next;
}
while(temp51!=null){
temp7.next=new Node(temp51.data);
temp51=temp51.next;
temp7=temp7.next;
}
while(temp61!=null){
temp7.next=new Node(temp61.data);
temp61=temp61.next;
temp7=temp7.next;
}
return temp8.next;
}
}
Time Complexity:O(N)[GFG Time:2.31/3.81]
Space Complexity:O(N)[LinkedList is given]
Auxiliary Space: O(N)[LinkedList creation and in the worst case can have a size equal to the given list size]
Total Test Cases:80
Approach used:
1. Create 3 small lists.(temp1, temp2, temp3)
2. Traverse the list(temp)
3. Add the elements in the sublist according to the nature of the element.
If the element value is less than x add in temp1
If the element value is equal to x add in temp2
If the element value is more than x add in temp3
4. Later merge all these three lists and return the final list(list7)
The creation of node temp41,temp51, and temp61 is to just avoid the values of -1.
eg given list is 1 2 4 5 6 6 4 4 3 2 and x=3
so temp will point to head og given list
temp1=-1
temp2=-1
temp3=-1
temp4=temp1
temp5=temp2
temp6=temp3
Now after traversing the list we get contents as
first sublist = -1->2->2 and temp2.next=null as temp2 is pointing to last 2
second sublist= -1->3 and temp2.next=null as temp2 is pointing to 3
third sublist= -1->4->5->6->6->4->4 and temp3.next=null as temp3 is pointing to last 4
Now in order to get the head values of these sublists we earlier created 3 additional nodes temp4, temp5, and temp6.
temp4=is pointing at the head of temp1 list ie -1->2->2
temp5= is pointing at the head of temp2 list ie -1->3
temp6= is pointing at the head of the temp3 list ie -1->4->5->6->6->4->4
Node temp7=new Node(-1) the final list which we will return
Now if we combine them after iterating the loop over them one by one we will get the output as:
temp7 list
-1->-1->2->2 -> -1->3 -> -1->4->5->6->6->4->4
which is the wrong output.
so for make it correct we do some changes:
1. To remove starting -1 we will do
Node temp8=temp7;
return temp8.next;
So now our modified output will be :
-1->2->2 -> -1->3 -> -1->4->5->6->6->4->4
2.To remove middle occuring ones we will use temp41 as temp4.next, temp51 as temp5.next and temp61 as temp6.next
Now our modified ouput will be
2->2 ->3 ->4->5->6->6->4->4
which is correct.
Solution 2:
class Solution {
public static Node partition(Node head, int x) {
Node temp=head;
Node temp1=new Node(-1);
Node temp2=new Node(-1);
Node temp3=new Node(-1);
Node temp41=temp1;
Node temp51=temp2;
Node temp61=temp3;
while(temp!=null){
if(temp.data<x){
temp1.next=new Node(temp.data);
temp=temp.next;
temp1=temp1.next;
}
else if(temp.data==x){
temp2.next=new Node(temp.data);
// temp2=temp2.next;
temp=temp.next;
temp2=temp2.next;
}
else{
temp3.next=new Node(temp.data);
// temp3=temp3.next;
temp=temp.next;
temp3=temp3.next;
}
}
temp41=temp41.next;
temp51=temp51.next;
temp61=temp61.next;
Node temp7= new Node(-1);
Node temp8=temp7;
while(temp41!=null){
temp7.next=new Node(temp41.data);
temp41=temp41.next;
temp7=temp7.next;
}
while(temp51!=null){
temp7.next=new Node(temp51.data);
temp51=temp51.next;
temp7=temp7.next;
}
while(temp61!=null){
temp7.next=new Node(temp61.data);
temp61=temp61.next;
temp7=temp7.next;
}
return temp8.next;
}
}
Time Complexity:O(N)[GFG Time:2.25/3.81]
Space Complexity:O(N)[LinkedList is given]
Auxiliary Space: O(N)[LinkedList creation and in the worst case can have a size equal to the given list size]
Total Test Cases:80
Approach Used:
Similar to the previous approach but slight modification as instead of declaring node4, node5 and node6 and later declaring node41 as node4.nextm node51 as node5.next and node61 as node6.next, we direclty create node41, node51 and node61 and we will modify as:
node41=node41.next
node51=node51.next
node61=node61.next
which will now not point to -1 instead it will point to the next element in those sublists they are referring to as node41 -> node1 node51->node2 and node61->node3
"Thanks For Reading.😇"
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment