Given a head of linked list containing nodes with values 0, 1, and 2 only, rearrange the list so that all 0s appear first, followed by all 1s, and then all 2s at the end, while maintaining the relative order within each group.
Examples:
Input:
Output: 0 → 1 → 1 → 2 →2 → 2 → 2 → 2 Explanation: All the 0s are segregated to the left end of the linked list, 2s to the right end of the list, and 1s in between.
Input:
Output: 0 → 1 → 2 → 2 Explanation: After arranging all the 0s, 1s and 2s in the given format, the output will be 0 -> 1 → 2 → 2.
[Naive Approach] Using an Extra Array - O(n × log n) Time and O(n) Space
The idea is to first convert the linked list into an array to easily leverage sorting, as sorting an array is straightforward and efficient. After sorting the array, we traverse the linked list again and reassign the sorted values back to the nodes.
C++
#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;classNode{public:intdata;Node*next;Node(intnew_data){data=new_data;next=nullptr;}};Node*segregate(Node*head){if(!head||!(head->next))returnhead;// convert linked list to arrayvector<int>arr;Node*curr=head;while(curr){arr.push_back(curr->data);curr=curr->next;}// sort the array sort(arr.begin(),arr.end());// reassign sorted values back to the linked listcurr=head;for(inti=0;i<arr.size();i++){curr->data=arr[i];curr=curr->next;}returnhead;}intmain(){Node*head=newNode(1);head->next=newNode(2);head->next->next=newNode(2);head->next->next->next=newNode(1);head->next->next->next->next=newNode(2);head->next->next->next->next->next=newNode(0);head->next->next->next->next->next->next=newNode(2);head->next->next->next->next->next->next->next=newNode(2);head=segregate(head);while(head!=nullptr){cout<<head->data;if(head->next!=nullptr){cout<<" -> ";}head=head->next;}cout<<"\n";return0;}
Java
importjava.util.ArrayList;importjava.util.Collections;classNode{intdata;Nodenext;Node(intnew_data){data=new_data;next=null;}}classGfG{staticNodesegregate(Nodehead){if(head==null||head.next==null)returnhead;// convert linked list to arrayArrayList<Integer>arr=newArrayList<>();Nodecurr=head;while(curr!=null){arr.add(curr.data);curr=curr.next;}// sort the array Collections.sort(arr);// reassign sorted values back to the linked listcurr=head;for(inti=0;i<arr.size();i++){curr.data=arr.get(i);curr=curr.next;}returnhead;}publicstaticvoidmain(String[]args){Nodehead=newNode(1);head.next=newNode(2);head.next.next=newNode(2);head.next.next.next=newNode(1);head.next.next.next.next=newNode(2);head.next.next.next.next.next=newNode(0);head.next.next.next.next.next.next=newNode(2);head.next.next.next.next.next.next.next=newNode(2);head=segregate(head);while(head!=null){System.out.print(head.data);if(head.next!=null){System.out.print(" -> ");}head=head.next;}System.out.println();}}
Python
classNode:def__init__(self,new_data):self.data=new_dataself.next=Nonedefsegregate(head):ifnotheadornothead.next:returnhead# convert linked list to arrayarr=[]curr=headwhilecurr:arr.append(curr.data)curr=curr.next# sort the array arr.sort()# reassign sorted values back to the linked listcurr=headforiinrange(len(arr)):curr.data=arr[i]curr=curr.nextreturnheadif__name__=="__main__":head=Node(1)head.next=Node(2)head.next.next=Node(2)head.next.next.next=Node(1)head.next.next.next.next=Node(2)head.next.next.next.next.next=Node(0)head.next.next.next.next.next.next=Node(2)head.next.next.next.next.next.next.next=Node(2)head=segregate(head)whilehead:print(str(head.data),end="")ifhead.next!=None:print(" -> ",end="")head=head.nextprint()
C#
usingSystem;usingSystem.Collections.Generic;classNode{publicintdata;publicNodenext;publicNode(intnew_data){data=new_data;next=null;}}classGfG{publicstaticNodesegregate(Nodehead){if(head==null||head.next==null)returnhead;// convert linked list to arrayList<int>arr=newList<int>();Nodecurr=head;while(curr!=null){arr.Add(curr.data);curr=curr.next;}// sort the array arr.Sort();// reassign sorted values back to the linked listcurr=head;for(inti=0;i<arr.Count;i++){curr.data=arr[i];curr=curr.next;}returnhead;}publicstaticvoidMain(){Nodehead=newNode(1);head.next=newNode(2);head.next.next=newNode(2);head.next.next.next=newNode(1);head.next.next.next.next=newNode(2);head.next.next.next.next.next=newNode(0);head.next.next.next.next.next.next=newNode(2);head.next.next.next.next.next.next.next=newNode(2);head=segregate(head);while(head!=null){Console.Write(head.data);if(head.next!=null){Console.Write(" -> ");}head=head.next;}Console.WriteLine();}}
JavaScript
classNode{constructor(new_data){this.data=new_data;this.next=null;}}functionsegregate(head){if(!head||!head.next)returnhead;// count the number of 0s, 1s, and 2sletcount=[0,0,0];letcurr=head;while(curr){count[curr.data]++;curr=curr.next;}// reassign values back to the linked listcurr=head;leti=0;while(curr){if(count[i]===0){i++;}else{curr.data=i;count[i]--;curr=curr.next;}}returnhead;}// Driver Codelethead=newNode(1);head.next=newNode(2);head.next.next=newNode(2);head.next.next.next=newNode(1);head.next.next.next.next=newNode(2);head.next.next.next.next.next=newNode(0);head.next.next.next.next.next.next=newNode(2);head.next.next.next.next.next.next.next=newNode(2);head=segregate(head);lettemp=head;while(temp){process.stdout.write(temp.data.toString());if(temp.next!==null){process.stdout.write(" -> ");}temp=temp.next;}console.log();
Output
0 -> 1 -> 1 -> 2 -> 2 -> 2 -> 2 -> 2
[Expected Approach - 1] Using Count of 0s, 1s and 2s - O(n) Time and O(1) Space
The idea is to traverse the linked list once and count the number of occurrences of 0s, 1s, and 2s. Once the counts are known, the linked list is traversed again, and the nodes are assigned the appropriate values based on the counts. First setting all nodes to 0, then to 1, and finally to 2.
C++
#include<iostream>usingnamespacestd;classNode{public:intdata;Node*next;Node(intnew_data){data=new_data;next=nullptr;}};Node*segregate(Node*head){if(!head||!(head->next))returnhead;// Initialize counts for 0s, 1s, and 2sintcntZero=0,cntOne=0,cntTwo=0;// Traverse the list to// count the occurrences of 0, 1, and 2Node*curr=head;while(curr){if(curr->data==0){cntZero++;}elseif(curr->data==1){cntOne++;}else{cntTwo++;}curr=curr->next;}// Rebuild the list with sorted valuescurr=head;// First add all the 0swhile(cntZero--){curr->data=0;curr=curr->next;}// Then add all the 1swhile(cntOne--){curr->data=1;curr=curr->next;}// Finally add all the 2swhile(cntTwo--){curr->data=2;curr=curr->next;}returnhead;}intmain(){Node*head=newNode(1);head->next=newNode(2);head->next->next=newNode(2);head->next->next->next=newNode(1);head->next->next->next->next=newNode(2);head->next->next->next->next->next=newNode(0);head->next->next->next->next->next->next=newNode(2);head->next->next->next->next->next->next->next=newNode(2);head=segregate(head);while(head!=nullptr){cout<<head->data;if(head->next!=nullptr){cout<<" -> ";}head=head->next;}cout<<"\n";return0;}
Java
classNode{intdata;Nodenext;Node(intnew_data){data=new_data;next=null;}}classGfG{staticNodesegregate(Nodehead){if(head==null||head.next==null)returnhead;// Initialize counts for 0s, 1s, and 2sintcntZero=0,cntOne=0,cntTwo=0;// Traverse the list to count the // occurrences of 0, 1, and 2Nodecurr=head;while(curr!=null){if(curr.data==0){cntZero++;}elseif(curr.data==1){cntOne++;}else{cntTwo++;}curr=curr.next;}// Rebuild the list with sorted valuescurr=head;// First add all the 0swhile(cntZero-->0){curr.data=0;curr=curr.next;}// Then add all the 1swhile(cntOne-->0){curr.data=1;curr=curr.next;}// Finally add all the 2swhile(cntTwo-->0){curr.data=2;curr=curr.next;}returnhead;}publicstaticvoidmain(String[]args){Nodehead=newNode(1);head.next=newNode(2);head.next.next=newNode(2);head.next.next.next=newNode(1);head.next.next.next.next=newNode(2);head.next.next.next.next.next=newNode(0);head.next.next.next.next.next.next=newNode(2);head.next.next.next.next.next.next.next=newNode(2);head=segregate(head);while(head!=null){System.out.print(head.data);if(head.next!=null){System.out.print(" -> ");}head=head.next;}System.out.println();}}
Python
classNode:def__init__(self,new_data):self.data=new_dataself.next=Nonedefsegregate(head):ifnotheadornothead.next:returnhead# initialize counts for 0s, 1s, and 2scntZero=0cntOne=0cntTwo=0# traverse the list to count the occurrences# of 0, 1, and 2curr=headwhilecurr:ifcurr.data==0:cntZero+=1elifcurr.data==1:cntOne+=1else:cntTwo+=1curr=curr.next# rebuild the list with sorted valuescurr=head# first add all the 0swhilecntZero:curr.data=0curr=curr.nextcntZero-=1# then add all the 1swhilecntOne:curr.data=1curr=curr.nextcntOne-=1# finally add all the 2swhilecntTwo:curr.data=2curr=curr.nextcntTwo-=1returnheadif__name__=="__main__":head=Node(1)head.next=Node(2)head.next.next=Node(2)head.next.next.next=Node(1)head.next.next.next.next=Node(2)head.next.next.next.next.next=Node(0)head.next.next.next.next.next.next=Node(2)head.next.next.next.next.next.next.next=Node(2)head=segregate(head)whilehead:print(str(head.data),end="")ifhead.next!=None:print(" -> ",end="")head=head.nextprint()
C#
usingSystem;usingSystem.Collections.Generic;classNode{publicintdata;publicNodenext;publicNode(intnew_data){data=new_data;next=null;}}classGfG{publicstaticNodesegregate(Nodehead){if(head==null||head.next==null)returnhead;// initialize counts for 0s, 1s, and 2sintcntZero=0,cntOne=0,cntTwo=0;// traverse the list to count the occurrences of 0, 1, and 2Nodecurr=head;while(curr!=null){if(curr.data==0){cntZero++;}elseif(curr.data==1){cntOne++;}else{cntTwo++;}curr=curr.next;}// rebuild the list with sorted valuescurr=head;// first add all the 0swhile(cntZero-->0){curr.data=0;curr=curr.next;}// then add all the 1swhile(cntOne-->0){curr.data=1;curr=curr.next;}// finally add all the 2swhile(cntTwo-->0){curr.data=2;curr=curr.next;}returnhead;}publicstaticvoidMain(){Nodehead=newNode(1);head.next=newNode(2);head.next.next=newNode(2);head.next.next.next=newNode(1);head.next.next.next.next=newNode(2);head.next.next.next.next.next=newNode(0);head.next.next.next.next.next.next=newNode(2);head.next.next.next.next.next.next.next=newNode(2);head=segregate(head);while(head!=null){Console.Write(head.data);if(head.next!=null){Console.Write(" -> ");}head=head.next;}Console.WriteLine();}}
JavaScript
classNode{constructor(new_data){this.data=new_data;this.next=null;}}functionsegregate(head){if(!head||!head.next)returnhead;// dummy nodes for 0s, 1s, and 2sletzeroD=newNode(-1),oneD=newNode(-1),twoD=newNode(-1);// current tails for 0s, 1s, and 2s listsletzero=zeroD,one=oneD,two=twoD;// traverse the original listletcurr=head;while(curr){if(curr.data===0){zero.next=curr;zero=zero.next;}elseif(curr.data===1){one.next=curr;one=one.next;}else{two.next=curr;two=two.next;}curr=curr.next;}// connect the three lists: 0s -> 1s -> 2szero.next=oneD.next?oneD.next:twoD.next;one.next=twoD.next;two.next=null;// new head will be next of dummy 0 nodereturnzeroD.next;}// Driver Codelethead=newNode(1);head.next=newNode(2);head.next.next=newNode(2);head.next.next.next=newNode(1);head.next.next.next.next=newNode(2);head.next.next.next.next.next=newNode(0);head.next.next.next.next.next.next=newNode(2);head.next.next.next.next.next.next.next=newNode(2);head=segregate(head);lettemp=head;while(temp){process.stdout.write(temp.data.toString());if(temp.next!=null){process.stdout.write(" -> ");}temp=temp.next;}console.log();
Output
0 -> 1 -> 1 -> 2 -> 2 -> 2 -> 2 -> 2
[Expected Approach - 2] By Changing Links of Nodes - O(n) Time and O(1) Space
The idea is to maintain 3 pointers named zero, one and two to point to current ending nodes of linked lists containing 0, 1, and 2 respectively. For every traversed node, we attach it to the end of its corresponding list.
If the current node's value is 0, append it after pointer zero and move pointer zero to current node.
If the current node's value is 1, append it after pointer one and move pointer one to current node.
If the current node's value is 2, append it after pointer two and move pointer two to current node.
Finally, we link all three lists. To avoid many null checks, we use three dummy pointers zeroD, oneD and twoD that work as dummy headers of three lists.
C++
#include<iostream>usingnamespacestd;classNode{public:intdata;Node*next;Node(intnew_data){data=new_data;next=nullptr;}};Node*segregate(Node*head){if(!head||!(head->next))returnhead;Node*zeroD=newNode(0);Node*oneD=newNode(0);Node*twoD=newNode(0);Node*zero=zeroD,*one=oneD,*two=twoD;// traverse list Node*curr=head;while(curr){if(curr->data==0){// if the data of current node is 0, // append it to pointer zero and update zerozero->next=curr;zero=zero->next;}elseif(curr->data==1){// if the data of current node is 1, // append it to pointer one and update oneone->next=curr;one=one->next;}else{// if the data of current node is 2, // append it to pointer two and update twotwo->next=curr;two=two->next;}curr=curr->next;}// combine the three listszero->next=(oneD->next)?(oneD->next):(twoD->next);one->next=twoD->next;two->next=NULL;// updated head head=zeroD->next;deletezeroD;deleteoneD;deletetwoD;returnhead;}intmain(){Node*head=newNode(1);head->next=newNode(2);head->next->next=newNode(2);head->next->next->next=newNode(1);head->next->next->next->next=newNode(2);head->next->next->next->next->next=newNode(0);head->next->next->next->next->next->next=newNode(2);head->next->next->next->next->next->next->next=newNode(2);head=segregate(head);while(head!=nullptr){cout<<head->data;if(head->next!=nullptr){cout<<" -> ";}head=head->next;}cout<<"\n";return0;}
Java
// a linked list nodeclassNode{intdata;Nodenext;Node(intnew_data){data=new_data;next=null;}}classGfG{staticNodesegregate(Nodehead){if(head==null||head.next==null)returnhead;NodezeroD=newNode(0);NodeoneD=newNode(0);NodetwoD=newNode(0);Nodezero=zeroD,one=oneD,two=twoD;// traverse list Nodecurr=head;while(curr!=null){if(curr.data==0){// if the data of current node is 0, // append it to pointer zero and update zerozero.next=curr;zero=zero.next;}elseif(curr.data==1){// if the data of current node is 1, // append it to pointer one and update oneone.next=curr;one=one.next;}else{// if the data of current node is 2, // append it to pointer two and update twotwo.next=curr;two=two.next;}curr=curr.next;}// combine the three listszero.next=(oneD.next!=null)?(oneD.next):(twoD.next);one.next=twoD.next;two.next=null;// updated head head=zeroD.next;returnhead;}publicstaticvoidmain(String[]args){Nodehead=newNode(1);head.next=newNode(2);head.next.next=newNode(2);head.next.next.next=newNode(1);head.next.next.next.next=newNode(2);head.next.next.next.next.next=newNode(0);head.next.next.next.next.next.next=newNode(2);head.next.next.next.next.next.next.next=newNode(2);head=segregate(head);while(head!=null){System.out.print(head.data);if(head.next!=null){System.out.print(" -> ");}head=head.next;}System.out.println();}}
Python
classNode:def__init__(self,new_data):self.data=new_dataself.next=Nonedefsegregate(head):ifnotheadornothead.next:returnheadzeroD=Node(0)oneD=Node(0)twoD=Node(0)# initialize current pointers for three # lists zero=zeroDone=oneDtwo=twoDcurr=headwhilecurr:ifcurr.data==0:# if the data of current node is 0, # append it to pointer zero and update zerozero.next=currzero=zero.nextelifcurr.data==1:# if the data of current node is 1, # append it to pointer one and update oneone.next=currone=one.nextelse:# if the data of current node is 2, # append it to pointer two and update twotwo.next=currtwo=two.nextcurr=curr.next# combine the three listszero.next=oneD.nextifoneD.nextelsetwoD.nextone.next=twoD.nexttwo.next=None# updated head head=zeroD.nextreturnheadif__name__=="__main__":head=Node(1)head.next=Node(2)head.next.next=Node(2)head.next.next.next=Node(1)head.next.next.next.next=Node(2)head.next.next.next.next.next=Node(0)head.next.next.next.next.next.next=Node(2)head.next.next.next.next.next.next.next=Node(2)head=segregate(head)whileheadisnotNone:print(head.data,end='')if(head.next!=None):print(" -> ",end="");head=head.nextprint()
C#
usingSystem;// a linked list nodepublicclassNode{publicintData;publicNodeNext;publicNode(intnewData){Data=newData;Next=null;}}publicclassGfG{publicstaticNodesegregate(Nodehead){if(head==null||head.Next==null)returnhead;NodezeroD=newNode(0);NodeoneD=newNode(0);NodetwoD=newNode(0);Nodezero=zeroD,one=oneD,two=twoD;// traverse list Nodecurr=head;while(curr!=null){if(curr.Data==0){// if the data of current node is 0, // append it to pointer zero and update zerozero.Next=curr;zero=zero.Next;}elseif(curr.Data==1){// if the data of current node is 1, // append it to pointer one and update oneone.Next=curr;one=one.Next;}else{// if the data of current node is 2, // append it to pointer two and update twotwo.Next=curr;two=two.Next;}curr=curr.Next;}// combine the three listszero.Next=(oneD.Next!=null)?(oneD.Next):(twoD.Next);one.Next=twoD.Next;two.Next=null;// updated head head=zeroD.Next;returnhead;}publicstaticvoidMain(){Nodehead=newNode(1);head.Next=newNode(2);head.Next.Next=newNode(2);head.Next.Next.Next=newNode(1);head.Next.Next.Next.Next=newNode(2);head.Next.Next.Next.Next.Next=newNode(0);head.Next.Next.Next.Next.Next.Next=newNode(2);head.Next.Next.Next.Next.Next.Next.Next=newNode(2);head=segregate(head);while(head!=null){Console.Write(head.Data);if(head.Next!=null){Console.Write(" -> ");}head=head.Next;}Console.WriteLine();}}
JavaScript
classNode{constructor(newData){this.data=newData;this.next=null;}}functionsegregate(head){if(!head||!head.next)returnhead;letzeroD=newNode(0);letoneD=newNode(0);lettwoD=newNode(0);letzero=zeroD,one=oneD,two=twoD;letcurr=head;while(curr){if(curr.data===0){// if the data of current node is 0, // append it to pointer zero and update zerozero.next=curr;zero=zero.next;}elseif(curr.data===1){// if the data of current node is 1, // append it to pointer one and update oneone.next=curr;one=one.next;}else{// if the data of current node is 2, // append it to pointer two and update twotwo.next=curr;two=two.next;}curr=curr.next;}// combine the three listszero.next=(oneD.next)?(oneD.next):(twoD.next);one.next=twoD.next;two.next=null;// updated head head=zeroD.next;returnhead;}// Driver codelethead=newNode(1);head.next=newNode(2);head.next.next=newNode(2);head.next.next.next=newNode(1);head.next.next.next.next=newNode(2);head.next.next.next.next.next=newNode(0);head.next.next.next.next.next.next=newNode(2);head.next.next.next.next.next.next.next=newNode(2);temp=segregate(head);while(temp){process.stdout.write(temp.data.toString());if(temp.next!=null){process.stdout.write(" -> ");}temp=temp.next;}console.log();
Output
0 -> 1 -> 1 -> 2 -> 2 -> 2 -> 2 -> 2
[Expected Approach - 3] Using Dutch National Flag Algorithm - O(n) Time and O(1) Space
The idea is to split the linked list into three separate sublists for 0s, 1s, and 2s using the Dutch National Flag algorithm. We maintain three dummy nodes and corresponding tail pointers to build each sublist during a single traversal. Once the segregation is done, we link these sublists in order: 0s -> 1s -> 2s. This avoids modifying node values and performs the operation in linear time and space.
Steps by step Implementation:
Create three dummy nodes to act as the start of separate lists for 0s, 1s, and 2s.
Initialize three tail pointers (zero, one, two) that point to the end of each of these sublists.
Traverse the original list and based on node value, append it to the respective sublist using tail pointers.
After appending a node, move the corresponding tail pointer forward to keep track of the last node.
Once traversal is complete, link zero list to one list and then link one list to two list carefully.
Ensure the last node of two list points to NULL to terminate the final merged list correctly.
Return the head of the combined list which starts from the next of zero dummy node.
C++
#include<iostream>usingnamespacestd;classNode{public:intdata;Node*next;Node(intnew_data){data=new_data;next=nullptr;}};Node*segregate(Node*head){if(!head||!(head->next)){returnhead;}Node*zeroD=newNode(-1);Node*oneD=newNode(-1);Node*twoD=newNode(-1);// Tails for the three listsNode*zero=zeroD;Node*one=oneD;Node*two=twoD;// Traverse the original listNode*curr=head;while(curr){if(curr->data==0){zero->next=curr;zero=zero->next;}elseif(curr->data==1){one->next=curr;one=one->next;}else{two->next=curr;two=two->next;}curr=curr->next;}// Connect the three lists togetherzero->next=oneD->next?oneD->next:twoD->next;one->next=twoD->next;two->next=nullptr;// New headhead=zeroD->next;deletezeroD;deleteoneD;deletetwoD;returnhead;}intmain(){Node*head=newNode(1);head->next=newNode(2);head->next->next=newNode(2);head->next->next->next=newNode(1);head->next->next->next->next=newNode(2);head->next->next->next->next->next=newNode(0);head->next->next->next->next->next->next=newNode(2);head->next->next->next->next->next->next->next=newNode(2);head=segregate(head);while(head!=nullptr){cout<<head->data;if(head->next!=nullptr){cout<<" -> ";}head=head->next;}cout<<"\n";return0;}
Java
classNode{intdata;Nodenext;Node(intnew_data){data=new_data;next=null;}}classGfG{staticNodesegregate(Nodehead){if(head==null||head.next==null){returnhead;}// Dummy nodes for three separate listsNodezeroD=newNode(-1);NodeoneD=newNode(-1);NodetwoD=newNode(-1);// Tails for the three listsNodezero=zeroD;Nodeone=oneD;Nodetwo=twoD;// Traverse the original listNodecurr=head;while(curr!=null){if(curr.data==0){zero.next=curr;zero=zero.next;}elseif(curr.data==1){one.next=curr;one=one.next;}else{two.next=curr;two=two.next;}curr=curr.next;}// Connect the three lists togetherzero.next=(oneD.next!=null)?oneD.next:twoD.next;one.next=twoD.next;two.next=null;// New headhead=zeroD.next;returnhead;}publicstaticvoidmain(String[]args){Nodehead=newNode(1);head.next=newNode(2);head.next.next=newNode(2);head.next.next.next=newNode(1);head.next.next.next.next=newNode(2);head.next.next.next.next.next=newNode(0);head.next.next.next.next.next.next=newNode(2);head.next.next.next.next.next.next.next=newNode(2);head=segregate(head);while(head!=null){System.out.print(head.data);if(head.next!=null){System.out.print(" -> ");}head=head.next;}System.out.println();}}
Python
classNode:def__init__(self,new_data):self.data=new_dataself.next=Nonedefsegregate(head):ifnotheadornothead.next:returnhead# Dummy nodes for three separate listszeroD=Node(-1)oneD=Node(-1)twoD=Node(-1)# Tails for the three listszero=zeroDone=oneDtwo=twoD# Traverse the original listcurr=headwhilecurr:ifcurr.data==0:zero.next=currzero=zero.nextelifcurr.data==1:one.next=currone=one.nextelse:two.next=currtwo=two.nextcurr=curr.next# Connect the three lists togetherzero.next=oneD.nextifoneD.nextelsetwoD.nextone.next=twoD.nexttwo.next=None# New headhead=zeroD.nextreturnheadif__name__=="__main__":head=Node(1)head.next=Node(2)head.next.next=Node(2)head.next.next.next=Node(1)head.next.next.next.next=Node(2)head.next.next.next.next.next=Node(0)head.next.next.next.next.next.next=Node(2)head.next.next.next.next.next.next.next=Node(2)head=segregate(head)whilehead:print(str(head.data),end="")ifhead.next!=None:print(" -> ",end="")head=head.nextprint()
C#
usingSystem;classNode{publicintdata;publicNodenext;publicNode(intnew_data){data=new_data;next=null;}}classGfG{publicstaticNodesegregate(Nodehead){if(head==null||head.next==null){returnhead;}NodezeroD=newNode(-1);NodeoneD=newNode(-1);NodetwoD=newNode(-1);// Tails for the three listsNodezero=zeroD;Nodeone=oneD;Nodetwo=twoD;// Traverse the original listNodecurr=head;while(curr!=null){if(curr.data==0){zero.next=curr;zero=zero.next;}elseif(curr.data==1){one.next=curr;one=one.next;}else{two.next=curr;two=two.next;}curr=curr.next;}// Connect the three lists togetherzero.next=(oneD.next!=null)?oneD.next:twoD.next;one.next=twoD.next;two.next=null;// New headhead=zeroD.next;returnhead;}publicstaticvoidMain(){Nodehead=newNode(1);head.next=newNode(2);head.next.next=newNode(2);head.next.next.next=newNode(1);head.next.next.next.next=newNode(2);head.next.next.next.next.next=newNode(0);head.next.next.next.next.next.next=newNode(2);head.next.next.next.next.next.next.next=newNode(2);head=segregate(head);while(head!=null){Console.Write(head.data);if(head.next!=null)Console.Write(" -> ");head=head.next;}Console.WriteLine();}}
JavaScript
functionNode(new_data){this.data=new_data;this.next=null;}functionsegregate(head){if(!head||!head.next){returnhead;}// dummy nodes for three separate listsletzeroD=newNode(-1);letoneD=newNode(-1);lettwoD=newNode(-1);// tails for the three listsletzero=zeroD;letone=oneD;lettwo=twoD;// traverse the original listletcurr=head;while(curr){if(curr.data===0){zero.next=curr;zero=zero.next;}elseif(curr.data===1){one.next=curr;one=one.next;}else{two.next=curr;two=two.next;}curr=curr.next;}// connect the three lists together correctlyzero.next=oneD.next?oneD.next:twoD.next;one.next=twoD.next;two.next=null;returnzeroD.next;}// Driver codelethead=newNode(1);head.next=newNode(2);head.next.next=newNode(2);head.next.next.next=newNode(1);head.next.next.next.next=newNode(2);head.next.next.next.next.next=newNode(0);head.next.next.next.next.next.next=newNode(2);head.next.next.next.next.next.next.next=newNode(2);head=segregate(head);lettemp=head;while(temp){process.stdout.write(temp.data.toString());if(temp.next!=null){process.stdout.write(" -> ");}temp=temp.next;}console.log();
