Sort linked list containing 0’s, 1’s, and 2’s in a single traversal
Given a linked list containing 0's, 1's, and 2's, sort the linked list by doing a single traversal of it.
For example,
Output: 0 —> 0 —> 0 —> 0 —> 0 —> 1 —> 1 —> 1 —> 1 —> 2 —> 2 —> 2 —> NULL
A simple solution would be to count the total number of 0's, 1's, and 2's present in the linked list, traverse the linked list, and put them back in the correct order. The problem with this approach is that we need to do two traversals of the list, which violates the problem constraints.
We can solve this problem in a single traversal of the list. The idea is to maintain three-pointers zeros, ones, and twos. Then, traverse the list from head to end and move each node to the corresponding list depending on its value. Finally, combine all three lists at the end and fix the head pointer.
The algorithm can be implemented as follows in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
#include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to create a new node with the given data and // pushes it onto the list's front void push(struct Node** head, int data) { // create a new linked list node from the heap struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = *head; *head = newNode; } // Helper function to print a given linked list void printList(struct Node* head) { struct Node* ptr = head; while (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; } printf("NULL"); } // Function to sort linked list containing 0's, 1's, and 2's // in a single traversal void sortList(struct Node** head) { // base case if (*head == NULL || (*head)->next == NULL) { return; } // maintain three dummy nodes struct Node dummyZero, dummyOne, dummyTwo; dummyZero.next = dummyOne.next = dummyTwo.next = NULL; // maintain three pointers struct Node* zero = &dummyZero, *one = &dummyOne, *two = &dummyTwo; struct Node* curr = *head; // traverse the list while (curr != NULL) { if (curr->data == 0) { zero->next = curr; zero = zero->next; } else if (curr->data == 1) { one->next = curr; one = one->next; } else { two->next = curr; two = two->next; } curr = curr->next; } // combine lists containing 0's, 1's, and 2's zero->next = (dummyOne.next)? (dummyOne.next): (dummyTwo.next); one->next = dummyTwo.next; two->next = NULL; // change head *head = dummyZero.next; } int main(void) { // input keys int keys[] = { 1, 2, 0, 0, 1, 2, 1, 2, 1 }; int n = sizeof(keys) / sizeof(keys[0]); struct Node* head = NULL; for (int i = n - 1; i >= 0; i--) { push(&head, keys[i]); } sortList(&head); printList(head); return 0; } |
Output:
0 —> 0 —> 1 —> 1 —> 1 —> 1 —> 2 —> 2 —> 2 —> NULL
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
// A Linked List Node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } Node() {} } class Main { // Helper function to print a given linked list public static void printList(Node head) { Node ptr = head; while (ptr != null) { System.out.print(ptr.data + " —> "); ptr = ptr.next; } System.out.println("null"); } // Function to sort linked list containing 0's, 1's, and 2's in a single traversal public static Node sortList(Node head) { // base case if (head == null || head.next == null) { return head; } // maintain three dummy nodes Node first = new Node(), second = new Node(), third = new Node(); // maintain three references Node zero = first, one = second, two = third; // traverse the list Node curr = head; while (curr != null) { if (curr.data == 0) { zero.next = curr; zero = zero.next; } else if (curr.data == 1) { one.next = curr; one = one.next; } else { two.next = curr; two = two.next; } curr = curr.next; } // combine lists containing 0's, 1's, and 2's zero.next = (second.next != null)? (second.next): (third.next); one.next = third.next; two.next = null; // change head return first.next; } public static void main(String[] args) { // input keys int[] keys = { 1, 2, 0, 0, 1, 2, 1, 2, 1 }; Node head = null; for (int i = keys.length - 1; i >= 0; i--) { head = new Node(keys[i], head); } head = sortList(head); printList(head); } } |
Output:
0 —> 0 —> 1 —> 1 —> 1 —> 1 —> 2 —> 2 —> 2 —> null
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
# A Linked List Node class Node: def __init__(self, data=None, next=None): self.data = data self.next = next # Function to print a given linked list def printList(head): ptr = head while ptr: print(ptr.data, end=' —> ') ptr = ptr.next print('None') # Function to sort linked list containing 0's, 1's, and 2's in a single traversal def sortList(head): # base case if head is None or head.next is None: return head # maintain three dummy nodes first = Node() second = Node() third = Node() # maintain three references zero = first one = second two = third # traverse the list curr = head while curr: if curr.data == 0: zero.next = curr zero = zero.next elif curr.data == 1: one.next = curr one = one.next else: two.next = curr two = two.next curr = curr.next # combine lists containing 0's, 1's, and 2's zero.next = second.next if second.next else third.next one.next = third.next two.next = None # change head and return return first.next if __name__ == '__main__': # input keys keys = [1, 2, 0, 0, 1, 2, 1, 2, 1] head = None for i in reversed(range(len(keys))): head = Node(keys[i], head) head = sortList(head) printList(head) |
Output:
0 —> 0 —> 1 —> 1 —> 1 —> 1 —> 2 —> 2 —> 2 —> None
The time complexity of the above solution is O(n), where n is the total number of nodes in the linked list, and doesn’t require any extra space.
Related Post:
Sort an array of 0’s, 1’s, and 2’s (Dutch National Flag Problem)
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)