Given the head of a Linked List of size N, consisting of binary integers 0s and 1s, the task is to sort the given linked list.
Examples:
Input: head = 1 -> 0 -> 1 -> 0 -> 1 -> 0 -> NULL
Output: 0 -> 0 -> 0 -> 1 -> 1 -> 1 -> NULLInput: head = 1 -> 1 -> 0 -> NULL
Output: 0 -> 1 -> 1 -> NULL
Naive Approach: The simplest approach to solve the given problem is to perform the merge sort or insertion sort on the given linked list and sort it. The Implementation of Sorting the Linked list using Merge sort and Sorting the linked list using Insertion sort is discussed already.
Time complexity: O(N * log N)
Auxiliary Space: O(N)
Better Approach: The simplest approach to solve the given problem can be to traverse the given linked list and store the values in the linked list in an array and then sort the array by using the sort function on array. Then traverse the linked list again and change the values of nodes by the values of array. In this way even the linked lists with values other than 0s and 1s can be sorted. Since the problem states that the linked list initially contain only 0s and 1s, so we can further optimize this approach.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Creating Link List Nodeclass Node {public: int data; Node* next;};// Function to print linked listvoid printList(Node* node){ // Iterate until node is NOT NULL while (node != NULL) { // Print the data cout << node->data << " "; node = node->next; // going to next node }}// Function to sort the linked list// consisting of 0s and 1svoid sortList(Node* head){ // Base Case if ((head == NULL) || (head->next == NULL)) { return; } vector<int> nums; Node* temp = head; while (temp != NULL) { // storing value of node into vector nums.push_back(temp->data); // Update the temp node temp = temp->next; } // sorting the nums array sort(nums.begin(), nums.end()); // Update the temp to head temp = head; int i = 0; // traversing the linked list while (i < nums.size()) { // updating value to nums[i] temp->data = nums[i]; // point temp to next node and increment i temp = temp->next; i++; }}// Function to push a nodevoid push(Node** head_ref, int new_data){ // Allocate node Node* new_node = new Node(); // Put in the data new_node->data = new_data; // Link the old list of the // new node new_node->next = (*head_ref); // Move the head to point to // the new node (*head_ref) = new_node;}// Driver Codeint main(void){ Node* head = NULL; // pushing values push(&head, 0); push(&head, 1); push(&head, 0); push(&head, 1); push(&head, 1); push(&head, 1); push(&head, 1); push(&head, 1); push(&head, 0); // printing linked list before and after sorting cout << "Linked List (before sorting) : "; printList(head); sortList(head); cout << "\nLinked List (after sorting) : "; printList(head); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class Node { int data; Node next;}class GFG { // Function to print linked list static void printList(Node node) { while (node != null) { System.out.print(node.data + " "); node = node.next; } } // Function to sort the linked list // consisting of 0s and 1s static void sortList(Node head) { // Base Case if (head == null || head.next == null) { return; } List<Integer> nums = new ArrayList<>(); Node temp = head; while (temp != null) { // storing value of node into list nums.add(temp.data); temp = temp.next; } // sorting the nums array Collections.sort(nums); temp = head; int i = 0; // traversing the linked list while (i < nums.size()) { temp.data = nums.get(i); temp = temp.next; i++; } } // Function to push a node static Node push(Node head, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head; return new_node; } public static void main(String[] args) { Node head = null; // pushing values head = push(head, 0); head = push(head, 1); head = push(head, 0); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 0); // printing linked list before and after sorting System.out.print("Linked List (before sorting) : "); printList(head); sortList(head); System.out.print( "\nLinked List (after sorting) : "); printList(head); }}// This code is contributed by lokesh. |
Python3
class Node: def __init__(self, data=None): """ Initialize the node with data and next pointer as None """ self.data = data self.next = None def printList(node): """ Function to print the linked list starting from the provided node """ # Iterate until node is NOT NULL while node: # Print the data print(node.data, end=' ') # Go to the next node node = node.nextdef sortList(head): """ Function to sort the linked list consisting of 0s and 1s """ # Base case if not head or not head.next: return nums = [] temp = head # Storing value of node into vector while temp: nums.append(temp.data) # Update the temp node temp = temp.next # sorting the nums array nums.sort() temp = head i = 0 # traversing the linked list while i < len(nums): # updating value to nums[i] temp.data = nums[i] # point temp to next node and increment i temp = temp.next i += 1def push(head, new_data): """ Add a new node with provided data to the front of the linked list """ new_node = Node(new_data) # Link the old list of the new node new_node.next = head return new_node# Driver codeif __name__ == '__main__': # pushing values head = None head = push(head, 0) head = push(head, 1) head = push(head, 0) head = push(head, 1) head = push(head, 1) head = push(head, 1) head = push(head, 1) head = push(head, 1) head = push(head, 0) # printing linked list before and after sorting print("Linked List (before sorting) : ", end=' ') printList(head) sortList(head) print("\nLinked List (after sorting) : ", end=' ') printList(head) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG { // Structure of a node class Node { public int data; public Node next; } // Function to print linked list static void PrintList(Node node) { while (node != null) { Console.Write(node.data + " "); node = node.next; } } // Function to sort the linked list // consisting of 0s and 1s static void SortList(ref Node head) { // Base Case if (head == null) { return; } List<int> nums = new List<int>(); Node temp = head; while (temp != null) { // storing value of node into list nums.Add(temp.data); temp = temp.next; } // sorting the nums array nums.Sort(); temp = head; int i = 0; // traversing the linked list while (i < nums.Count) { temp.data = nums[i]; temp = temp.next; i++; } } // Function to push a node static Node Push(Node head, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head; return new_node; } static public void Main() { // Code Node head = null; // pushing values head = Push(head, 0); head = Push(head, 1); head = Push(head, 0); head = Push(head, 1); head = Push(head, 1); head = Push(head, 1); head = Push(head, 1); head = Push(head, 1); head = Push(head, 0); // printing linked list before and after sorting Console.Write("Linked List (before sorting) : "); PrintList(head); SortList(ref head); Console.Write("\nLinked List (after sorting) : "); PrintList(head); }}// This code is contributed by lokeshmvs21. |
Javascript
<script> // JavaScript program for the above approach class Node { constructor(data) { this.data = data; this.next = null; } } // Function to print linked list function printList(node) { let curr = node; let str = ""; while (curr !== null) { str += curr.data + " "; curr = curr.next; } document.write(str); } // Function to sort the linked list consisting of 0s and 1s function sortList(head) { // Base Case if (!head || !head.next) { return; } let nums = []; let curr = head; while (curr !== null) { // storing value of node into list nums.push(curr.data); curr = curr.next; } // sorting the nums array nums.sort(function(a, b) { return a - b; }); curr = head; let i = 0; // traversing the linked list while (i < nums.length) { curr.data = nums[i]; curr = curr.next; i++; } } // Function to push a node function push(head, newData) { let newNode = new Node(); newNode.data = newData newNode.next = head; return newNode; } let head = null; // pushing values head = push(head, 0); head = push(head, 1); head = push(head, 0); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 0); // printing the linked list before and after sorting document.write("Linked List (before sorting) : "); printList(head); sortList(head); document.write("<br>Linked List (after sorting) : "); printList(head); // This code is contributed by lokeshmvs21.</script> |
Output
Linked List (before sorting) : 0 1 1 1 1 1 0 1 0 Linked List (after sorting) : 0 0 0 1 1 1 1 1 1
Time complexity: O(N * log N)
Auxiliary Space: O(N)
Efficient Approach: The above approach can also be optimized by counting the number of 1s and 0s in the given linked list and update the value of nodes accordingly in the linked list. Follow the steps to solve the problem:
- Traverse the given linked list and store the count of 0s and 1s in variables, say zeroes and ones respectively.
- Now, traverse the linked list again and change the first zeroes nodes with value 0 and then the remaining nodes with the value 1.
- After completing the above steps, print the linked list as the resultant sorted list.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Link list nodeclass Node {public: int data; Node* next;};// Function to print linked listvoid printList(Node* node){ // Iterate until node is NOT NULL while (node != NULL) { // Print the data cout << node->data << " "; node = node->next; }}// Function to sort the linked list// consisting of 0s and 1svoid sortList(Node* head){ // Base Case if ((head == NULL) || (head->next == NULL)) { return; } // Store the count of 0s and 1s int count0 = 0, count1 = 0; // Stores the head node Node* temp = head; // Traverse the list Head while (temp != NULL) { // If node->data value is 0 if (temp->data == 0) { // Increment count0 by 1 count0++; } // Otherwise, increment the // count of 1s else { count1++; } // Update the temp node temp = temp->next; } // Update the temp to head temp = head; // Traverse the list and update // the first count0 nodes as 0 while (count0--) { temp->data = 0; temp = temp->next; } // Now, update the value of the // remaining count1 nodes as 1 while (count1--) { temp->data = 1; temp = temp->next; }}// Function to push a nodevoid push(Node** head_ref, int new_data){ // Allocate node Node* new_node = new Node(); // Put in the data new_node->data = new_data; // Link the old list of the // new node new_node->next = (*head_ref); // Move the head to point to // the new node (*head_ref) = new_node;}// Driver Codeint main(void){ Node* head = NULL; push(&head, 0); push(&head, 1); push(&head, 0); push(&head, 1); push(&head, 1); push(&head, 1); push(&head, 1); push(&head, 1); push(&head, 0); cout << "Linked List (before sorting) : "; printList(head); sortList(head); cout << "\nLinked List (after sorting) : "; printList(head); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Link list node static class Node { int data; Node next; }; // Function to print linked list static void printList(Node node) { // Iterate until node is NOT null while (node != null) { // Print the data System.out.print(node.data+ " "); node = node.next; } } // Function to sort the linked list // consisting of 0s and 1s static void sortList(Node head) { // Base Case if ((head == null) || (head.next == null)) { return; } // Store the count of 0s and 1s int count0 = 0, count1 = 0; // Stores the head node Node temp = head; // Traverse the list Head while (temp != null) { // If node.data value is 0 if (temp.data == 0) { // Increment count0 by 1 count0++; } // Otherwise, increment the // count of 1s else { count1++; } // Update the temp node temp = temp.next; } // Update the temp to head temp = head; // Traverse the list and update // the first count0 nodes as 0 while (count0>0) { temp.data = 0; temp = temp.next; count0--; } // Now, update the value of the // remaining count1 nodes as 1 while (count1>0) { temp.data = 1; temp = temp.next; count1--; } // Print the Linked List printList(head); } // Function to push a node static Node push(Node head_ref, int new_data) { // Allocate node Node new_node = new Node(); // Put in the data new_node.data = new_data; // Link the old list of the // new node new_node.next = head_ref; // Move the head to point to // the new node head_ref = new_node; return head_ref; } // Driver Code public static void main(String[] args) { Node head = null; head = push(head, 0); head = push(head, 1); head = push(head, 0); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 0); sortList(head); }}// This code is contributed by umadevi9616 |
Python3
# Python program for the above approach# Link list Nodeclass Node: def __init__(self): self.data = 0; self.next = None;# Function to print linked listdef printList(Node): # Iterate until Node is NOT None while (Node != None): # Print data print(Node.data, end=" "); Node = Node.next; # Function to sort the linked list# consisting of 0s and 1sdef sortList(head): # Base Case if ((head == None) or (head.next == None)): return; # Store the count of 0s and 1s count0 = 0; count1 = 0; # Stores the head Node temp = head; # Traverse the list Head while (temp != None): # If Node.data value is 0 if (temp.data == 0): # Increment count0 by 1 count0 += 1; # Otherwise, increment the # count of 1s else: count1 += 1; # Update the temp Node temp = temp.next; # Update the temp to head temp = head; # Traverse the list and update # the first count0 Nodes as 0 while (count0 > 0): temp.data = 0; temp = temp.next; count0 -= 1; # Now, update the value of the # remaining count1 Nodes as 1 while (count1 > 0): temp.data = 1; temp = temp.next; count1 -= 1; # Print the Linked List printList(head);# Function to push a Nodedef push(head_ref, new_data): # Allocate Node new_Node = Node(); # Put in the data new_Node.data = new_data; # Link the old list of the # new Node new_Node.next = head_ref; # Move the head to point to # the new Node head_ref = new_Node; return head_ref;# Driver Codeif __name__ == '__main__': head = None; head = push(head, 0); head = push(head, 1); head = push(head, 0); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 0); sortList(head);# This code is contributed by umadevi9616 |
C#
// C# program for the above approachusing System;public class GFG { // Link list nodepublic class Node { public int data; public Node next; }; // Function to print linked list static void printList(Node node) { // Iterate until node is NOT null while (node != null) { // Print the data Console.Write(node.data + " "); node = node.next; } } // Function to sort the linked list // consisting of 0s and 1s static void sortList(Node head) { // Base Case if ((head == null) || (head.next == null)) { return; } // Store the count of 0s and 1s int count0 = 0, count1 = 0; // Stores the head node Node temp = head; // Traverse the list Head while (temp != null) { // If node.data value is 0 if (temp.data == 0) { // Increment count0 by 1 count0++; } // Otherwise, increment the // count of 1s else { count1++; } // Update the temp node temp = temp.next; } // Update the temp to head temp = head; // Traverse the list and update // the first count0 nodes as 0 while (count0 > 0) { temp.data = 0; temp = temp.next; count0--; } // Now, update the value of the // remaining count1 nodes as 1 while (count1 > 0) { temp.data = 1; temp = temp.next; count1--; } // Print the Linked List printList(head); } // Function to push a node static Node push(Node head_ref, int new_data) { // Allocate node Node new_node = new Node(); // Put in the data new_node.data = new_data; // Link the old list of the // new node new_node.next = head_ref; // Move the head to point to // the new node head_ref = new_node; return head_ref; } // Driver Code public static void Main(String[] args) { Node head = null; head = push(head, 0); head = push(head, 1); head = push(head, 0); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 0); sortList(head); }}// This code is contributed by umadevi9616 |
Javascript
<script>// javascript program for the above approach // Link list nodeclass Node { constructor() { this.data = 0; this.next = null; }} // Function to print linked list function printList(node) { // Iterate until node is NOT null while (node != null) { // Print the data document.write(node.data + " "); node = node.next; } } // Function to sort the linked list // consisting of 0s and 1s function sortList(head) { // Base Case if ((head == null) || (head.next == null)) { return; } // Store the count of 0s and 1s var count0 = 0, count1 = 0; // Stores the head node var temp = head; // Traverse the list Head while (temp != null) { // If node.data value is 0 if (temp.data == 0) { // Increment count0 by 1 count0++; } // Otherwise, increment the // count of 1s else { count1++; } // Update the temp node temp = temp.next; } // Update the temp to head temp = head; // Traverse the list and update // the first count0 nodes as 0 while (count0 > 0) { temp.data = 0; temp = temp.next; count0--; } // Now, update the value of the // remaining count1 nodes as 1 while (count1 > 0) { temp.data = 1; temp = temp.next; count1--; } // Print the Linked List printList(head); } // Function to push a node function push(head_ref , new_data) { // Allocate node var new_node = new Node(); // Put in the data new_node.data = new_data; // Link the old list of the // new node new_node.next = head_ref; // Move the head to point to // the new node head_ref = new_node; return head_ref; } // Driver Code var head = null; head = push(head, 0); head = push(head, 1); head = push(head, 0); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 0); sortList(head); // This code is contributed by umadevi9616</script> |
Output:
0 0 0 1 1 1 1 1 1
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Info to that Topic: geeksforgeeks.org/sort-a-linked-list-of-0s-and-1s/ […]