Sort a linked list of 0s, 1s, and 2s by changing links

In this article, we will learn to sort a linked list of 0s 1s and 2s. Sorting an array implies that the elements present in the array must be present in a particular order, whether in ascending order or in descending order. Let’s try to understand to sort linked list of 0 1 2

Problem Statement

In this problem, we are given a linked list containing 0s, 1s, and 2s, and we are required to sort this linked list.

Example

Input:

Output:

Problem Statement Understanding to sort a linked list of 0s 1s and 2s

Let’s learn programming languages online and try to understand to sort linked of 01 2

Suppose we are given a linked list 1 → 2 → 0 → 1 → 0 → NULL, now the problem is demanding that we have to sort the linked list such that our original linked list after sorting should look like:
Final resultant linked list after sorting:- 0 → 0 → 1 → 1 → 2 → NULL

Explanation: So basically we have to sort the linked list such that in the final sorted linked list all the nodes with value 0 come before the nodes with value 1 and all the nodes with value 1 comes before the nodes with value 2.

Say if the input linked list is

now in this case after sorting the input linked list our final linked list will look like:
Final resultant linked list after sorting:-

So now I think from the above examples it is clear what the problem is demanding to sort a linked list of 0 1 2.

Let’s think how we can approach to sort a linked list of 0s 1s and 2s.

Approach 1 to sort linked list of 0 1 2

As we can see in the problem our linked list only contains nodes with values 0, 1, and 2, so one simple solution will be to count the number of 0’s, 1’s, and 2’s.

  • After counting the number of 0’s, 1’s, and 2’s, fill the first P (where P is count of 0’s) nodes with 0, then next Q (where Q is count of 1’s) nodes with 1 and last R (where R is count of 2’s) nodes with 2.

  • After filling the nodes with 0’s, 1’s, and 2’s, our final linked list will be sorted, and we will get our desired result.

But there is one problem, that this solution does not work when these values have associated data with them.

  • For example, If these three 0’s, 1’s, and 2’s represent three different colors and with these colors different types of objects have been associated and have to sort the objects based on colors.

So now we will see how can we solve this problem and finally sort the list.

Approach 2 to sort linked list of 0 1 2

The above problem could be solved by changing the links:

  • If we can change the links of nodes such that all the nodes having value of 0 gets together and forms a separate linked list containing all the nodes with value 0. Similarly, the nodes with values 1 and 2 also get together and form their separate linked list.
  • After separate linked lists for 0’s, 1’s, and 2’s have been formed:
    1) We will make the head of the linked list containing 0’s the head of the final sorted linked list.
    2) We will make the tail of the linked list of 0’s point to the head of the linked list of 1’s and the tail of the linked list of 1’s point to the head of the linked list of 2’s.
    3) Also, we will make the tail of the linked list of 2’s point to NULL.
  • Finally, we can return our final sorted linked list by returning the head of a linked list of 0’s.

Algorithm to sort a linked list of 0s 1s and 2s

  • Traverse through the list one by one.
  • Maintain three pointers designated ptr0, ptr1, and ptr2 that refer to the current ending nodes of linked lists with 0, 1, and 2 elements, respectively.
  • We append each explored Node to the end of its associated list:
    1) Node with value 0 will be appended to the end of linked list of 0’s.
    2) Node with value 1 will be appended to end of linked list of 1’s.
    3) Node with value 2 will be appended to the end of linked lists of 2’s.
  • Finally, we join the three lists together. For joining the three lists together we will utilize three dummy pointers temp0, temp1, and temp2 that act as dummy headers for the three lists to avoid multiple null tests.
  • Finally, we will return the head of the linked list of 0’s.

Dry Run to sort a linked list of 0s 1s and 2s

Code Implementation to sort a linked list of 0 1 2

#include <stdio.h>
#include<stdlib.h>
 
struct Node {
    int data;
    struct Node* next;
};
 
struct Node* newNode(int data);
 
// Sort a linked list of 0s, 1s and 2s
// by changing pointers.
struct Node* sortList(struct Node* head)
{
    if (!head || !(head->next))
        return head;
 
    // Create three dummy nodes to point to
    // beginning of three linked lists. These
    // dummy nodes are created to avoid many
    // null checks.
    struct Node* zeroD = newNode(0);
    struct Node* oneD = newNode(0);
    struct Node* twoD = newNode(0);
 
    // Initialize current pointers for three
    // lists and whole list.
    struct Node* zero = zeroD, *one = oneD, *two = twoD;
 
    // Traverse list
    struct Node* curr = head;
    while (curr) {
        if (curr->data == 0) {
            zero->next = curr;
            zero = zero->next;
            curr = curr->next;
        } else if (curr->data == 1) {
            one->next = curr;
            one = one->next;
            curr = curr->next;
        } else {
            two->next = curr;
            two = two->next;
            curr = curr->next;
        }
    }
 
    // Attach three lists
    zero->next = (oneD->next)
? (oneD->next) : (twoD->next);
    one->next = twoD->next;
    two->next = NULL;
 
    // Updated head
    head = zeroD->next;
 
    // Delete dummy nodes
    free(zeroD);
    free(oneD);
    free(twoD);
 
    return head;
}
 
// Function to create and return a node
struct Node* newNode(int data)
{
    // allocating space
    struct Node* newNode =
         (struct Node*)malloc(sizeof(struct Node));
 
    // inserting the required data
    newNode->data = data;
    newNode->next = NULL;
}
 
/* Function to print linked list */
void printList(struct Node* node)
{
    while (node != NULL) {
        printf("%d  ", node->data);
        node = node->next;
    }
    printf("\n");
}
 
/* Driver program to test above function*/
int main(void)
{
    // Creating the list 1->2->4->5
    struct Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(0);
    head->next->next->next = newNode(1);
 
    printf("Linked List Before Sorting\n");
    printList(head);
 
    head = sortList(head);
 
    printf("Linked List After Sorting\n");
    printList(head);
 
    return 0;
}
#include <bits/stdc++.h>
using namespace std;

/* node definition */
struct Node {
    int val;
    struct Node* next;
};

Node* newNode(int val);

// Sorting 0s, 1s and 2s in a linked list
Node* sortingLL(Node* head)
{
    if (!head || !(head->next))
        return head;

// Creating three dummy nodes inorder to point
// to the starting of the 3 lists. 
// Their motive is to help in avoiding null checks.
    Node* temp0 = newNode(0);
    Node* temp1 = newNode(0);
    Node* temp2 = newNode(0);

    // Initialize current pointers
    Node* ptr0 = temp0, *ptr1 = temp1, *ptr2 = temp2;

    // Traversing through the list
    Node* current = head;
    while (current) {
        if (current->val == 0) {
            ptr0->next = current;
            ptr0 = ptr0->next;
            current = current->next;
        } else if (current->val == 1) {
            ptr1->next = current;
            ptr1 = ptr1->next;
            current = current->next;
        } else {
            ptr2->next = current;
            ptr2 = ptr2->next;
            current = current->next;
        }
    }

    // connect the 2 linked lists.
    ptr0->next = (temp1->next)
    ? (temp1->next) : (temp2->next);
    ptr1->next = temp2->next;
    ptr2->next = NULL;

    // Updating the head
    head = temp0->next;

    // Deletion of dummy nodes
    delete temp0;
    delete temp1;
    delete temp2;

    return head;
}

// Creating and returning a node.
Node* newNode(int val)
{
    Node* newNode = new Node;
    newNode->val = val;
    newNode->next = NULL;
}

// Function to display the Linked List
void displayList(struct Node* node)
{
    while (node != NULL) {
        cout<<node->val<<” “;
        node = node->next;
    }
    cout<<endl;
}

// Driver function
int main()
{
    // Creation of list
    Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(0);
    head->next->next->next = newNode(1);
     head->next->next->next->next = newNode(0);

    cout<<"Original Linked List:”<<endl;
    displayList(head);

    head = sortingLL(head);

    cout<<"Sorted Linked List:”<<endl;
    displayList(head);

    return 0;
}



class Node
{
	int data;
	Node next;
	Node(int data)
	{
		this.data=data;
	}
}


class SortIt 
{
	public static Node sortList(Node head)
	{
		if(head==null || head.next==null)
		{
			return head;
		}
		Node zeroD = new Node(0);
		Node oneD = new Node(0);
		Node twoD = new Node(0);

		Node zero = zeroD, one = oneD, two = twoD;
		Node curr = head;
		while (curr!=null)
		{
			if (curr.data == 0)
			{
				zero.next = curr;
				zero = zero.next;
				curr = curr.next;
			}
			else if (curr.data == 1)
			{
				one.next = curr;
				one = one.next;
				curr = curr.next;
			}
			else
			{
				two.next = curr;
				two = two.next;
				curr = curr.next;
			}
		}
		zero.next = (oneD.next!=null)? (oneD.next) : (twoD.next);
		one.next = twoD.next;
		two.next = null;
		head = zeroD.next;
		return head;
	}
	// function to create and return a node
	public static Node newNode(int data)
	{
		// allocating space
		Node newNode = new Node(data);
		newNode.next = null;
		return newNode;
	}
	/* Function to print linked list */
	public static void printList(Node node)
	{
		while (node != null)
		{
			System.out.print(node.data+" ");
			node = node.next;
		}
	}
	public static void main(String args[]) 
    {
		Node head = new Node(1);
		head.next = new Node(2);
		head.next.next = new Node(0);
		head.next.next.next = new Node(1);
		System.out.println("Linked List Before Sorting");
		printList(head);
		head = sortList(head);
		System.out.println("Linked List After Sorting");
		printList(head);
	}
}


# Link list node
class Node:
	def __init__(self, data):
		self.data = data
		self.next = None

# Sort a linked list of 0s, 1s and 2s
# by changing poers.
def sortList(head):
	if (head == None or
		head.next == None):
		return head

	# Create three dummy nodes to point to
	# beginning of three linked lists.
	# These dummy nodes are created to
	# avoid many None checks.
	zeroD = Node(0)
	oneD = Node(0)
	twoD = Node(0)

	# Initialize current pointers for three
	# lists and whole list.
	zero = zeroD
	one = oneD
	two = twoD

	# Traverse list
	curr = head
	while (curr):
		if (curr.data == 0):
			zero.next = curr
			zero = zero.next
			curr = curr.next
		elif(curr.data == 1):
			one.next = curr
			one = one.next
			curr = curr.next
		else:
			two.next = curr
			two = two.next
			curr = curr.next
		
	# Attach three lists
	zero.next = (oneD.next) if (oneD.next ) \
							else (twoD.next)
	one.next = twoD.next
	two.next = None

	# Updated head
	head = zeroD.next

	# Delete dummy nodes
	return head

# function to create and return a node
def newNode(data):
	
	newNode = Node(data)
	newNode.data = data
	newNode.next = None
	return newNode

# Function to print linked list
def printList(node):
	while (node != None):
		print(node.data, end = " ")
		node = node.next
	
if __name__=='__main__':
	
	# Creating the list 1.2.4.5
	head = newNode(1)
	head.next = newNode(2)
	head.next.next = newNode(0)
	head.next.next.next = newNode(1)
	head.next.next.next.next = newNode(0)

	print("Linked List Before Sorting")
	printList(head)

	head = sortList(head)

	print("\nLinked List After Sorting")
	printList(head)

Output:

Original Linked List:
1 2 0 1 0
Sorted Linked List:
0 0 1 1 2

Time Complexity: O(n), where n is the number of nodes in the linked list.

In this article, we have explained how to sort a linked list of 0s 1s and 2s. Different approaches have been explained to sort linked list of 0 1 2 with pictorial dry run and code implementation with all time and space complexities. To explore more on the linked list you can follow this link Linked List, which is curated by our expert mentors at PrepBytes Footer

Related Articles
Doubly circular linked list in data structure Application of doubly linked list
Applications of linked list Singly linked list vs doubly linked list
Advantages and disadvantages of linked list Doubly linked list all operations in C
Binary search in linked list Bubble sort linked list
Deletion in doubly linked list Delete the middle node of a linked list
Polynomial addition using linked list Find max value and min value in linked list
Insert a node at a specific position in a linked list Swap nodes in linked list
Add two numbers represented by linked lists Find starting point of loop in linked list
Merge sort linked list Delete a node from linked list at a given position
Remove duplicates from unsorted linked list Reverse a linked list in Python

FAQs to sort a linked list of 0s 1s and 2s

  1. Can we reverse a linked list in less than O(N)?

  2. It is not possible to reverse a simple singly linked list in less than O(n).

  3. What is a linked list?

  4. A linked list is a sequence of data structures, which are connected together via links and each node points to the next node.

  5. Is the linked list allow null values?

  6. The linked list allows any number of null values while LinkedHashSet also allows a maximum of one null element.

Leave a Reply

Your email address will not be published. Required fields are marked *