Open In App

Sort a linked list of 0s, 1s and 2s

Last Updated : 27 Aug, 2024
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow

Given a linked list of 0s, 1s and 2s, The task is to sort the list in non-decreasing order.

Examples: 

Input: 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> NULL
Output: 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2 -> NULL

Input: 1 -> 1 -> 2 -> 1 -> 0 -> NULL
Output: 0 -> 1 -> 1 -> 1 -> 2 -> NULL 

[Expected Approach – 1] By Maintaining Frequency – O(n) Time and O(1) Space:

The idea is to traverse the linked List and count the number of nodes having values 0, 1 and 2 and store them in an array of size 3, say cnt[] such that

  • cnt[0] = count of nodes with value 0
  • cnt[1] = count of nodes with value 1
  • cnt[2] = count of nodes with value 2

Now, traverse the linked list again to fill the first cnt[0] nodes with 0, then next cnt[1] nodes with 1 and finally cnt[2] nodes with 2.

Below is the illustration of above approach :


Below is the implementation of the above approach.

C++ 
// C++ Program to sort a linked list of 0s, 1s or 2s

#include <bits/stdc++.h>
using namespace std;

class Node {
  public:
    int data;
    Node *next;
   
    Node(int new_data) {
        data = new_data;
        next = nullptr;
    }
};

// Function to sort a linked list of 0s, 1s and 2s
void sortList(Node* head) {

    // Initialize count of '0', '1' and '2' as 0
    int cnt[3] = {0, 0, 0};
    Node *ptr = head;

    // Traverse and count total number of '0', '1' and '2'
    // cnt[0] will store total number of '0's
    // cnt[1] will store total number of '1's
    // cnt[2] will store total number of '2's
    while (ptr != NULL) {
        cnt[ptr->data] += 1;
        ptr = ptr->next;
    }

    int idx = 0;
    ptr = head;

    // Fill first cnt[0] nodes with value 0
    // Fill next cnt[1] nodes with value 1
    // Fill remaining cnt[2] nodes with value 2
    while (ptr != nullptr) {

        if (cnt[idx] == 0)
            idx += 1;
        else {
            ptr->data = idx;
            cnt[idx] -= 1;
            ptr = ptr->next;
        }
    }
}

void printList(Node *node) {
    while (node != nullptr) {
        cout << " " << node->data;
        node = node->next;
    }
    cout << "\n";
}


int main() {

    // Create a hard-coded linked list:
    // 1 -> 1 -> 2 -> 1 -> 0 -> NULL 
    Node *head = new Node(1);
    head->next = new Node(1);
    head->next->next = new Node(2);
    head->next->next->next = new Node(1);
    head->next->next->next->next = new Node(0);

    cout << "Linked List before Sorting:";
    printList(head);

    sortList(head);

    cout << "Linked List after Sorting:";
    printList(head);

    return 0;
}
C 
// C Program to sort a linked list of 0s, 1s or 2s

#include <stdio.h>

struct Node {
    int data;
    struct Node *next;
};


// Function to sort a linked list of 0s, 1s and 2s
void sortList(struct Node *head) {

    // Initialize count of '0', '1' and '2' as 0
    int cnt[3] = {0, 0, 0};
    struct Node *ptr = head;

    // Traverse and count total number of '0', '1' and '2'
    // cnt[0] will store total number of '0's
    // cnt[1] will store total number of '1's
    // cnt[2] will store total number of '2's
    while (ptr != NULL) {
        cnt[ptr->data] += 1;
        ptr = ptr->next;
    }

    int idx = 0;
    ptr = head;

    // Fill first cnt[0] nodes with value 0
    // Fill next cnt[1] nodes with value 1
    // Fill remaining cnt[2] nodes with value 2
    while (ptr != NULL) {
        if (cnt[idx] == 0) {
            idx += 1;
        }
        else {
            ptr->data = idx;
            cnt[idx] -= 1;
            ptr = ptr->next;
        }
    }
}

void printList(struct Node *node) {
    while (node != NULL) {
        printf(" %d", node->data);
        node = node->next;
    }
    printf("\n");
}

struct Node *createNode(int new_data) {
    struct Node *new_node = 
      (struct Node *)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = NULL;
    return new_node;
}

int main() {

    // Create a hard-coded linked list:
    // 1 -> 1 -> 2 -> 1 -> 0 -> NULL
    struct Node *head = createNode(1);
    head->next = createNode(1);
    head->next->next = createNode(2);
    head->next->next->next = createNode(1);
    head->next->next->next->next = createNode(0);

    printf("Linked List before Sorting:");
    printList(head);

    sortList(head);

    printf("Linked List after Sorting:");
    printList(head);

    return 0;
}
Java 
// Java Program to sort a linked list of 0s, 1s or 2s

class Node {
    int data;
    Node next;
    Node(int new_data) {
        data = new_data;
        next = null;
    }
}

// Function to sort a linked list of 0s, 1s and 2s
class GfG {
  
    static void sortList(Node head) {
      
        // Initialize count of '0', '1' and '2' as 0
        int[] cnt = { 0, 0, 0 };
        Node ptr = head;

        // Traverse and count total number of '0', '1' and '2'
        // cnt[0] will store total number of '0's
        // cnt[1] will store total number of '1's
        // cnt[2] will store total number of '2's
        while (ptr != null) {
            cnt[ptr.data] += 1;
            ptr = ptr.next;
        }

        int idx = 0;
        ptr = head;
        
        // Fill first cnt[0] nodes with value 0
        // Fill next cnt[1] nodes with value 1
        // Fill remaining cnt[2] nodes with value 2
        while (ptr != null) {
            if (cnt[idx] == 0)
                idx += 1;
            else {
                ptr.data = idx;
                cnt[idx] -= 1;
                ptr = ptr.next;
            }
        }
    }

    static void printList(Node node) {
        while (node != null) {
            System.out.print(" " + node.data);
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
      
        // Create a hard-coded linked list:
        // 1 -> 1 -> 2 -> 1 -> 0 -> NULL
        Node head = new Node(1);
        head.next = new Node(1);
        head.next.next = new Node(2);
        head.next.next.next = new Node(1);
        head.next.next.next.next = new Node(0);

        System.out.print("Linked List before Sorting:");
        printList(head);

        sortList(head);

        System.out.print("Linked List after Sorting:");
        printList(head);
    }
}
Python 
# Python Program to sort a linked list of 0s, 1s or 2s

class Node:
    def __init__(self, new_data):
        self.data = new_data
        self.next = None

# Function to sort a linked list of 0s, 1s and 2s
def sort_list(head):
  
    # Initialize count of '0', '1' and '2' as 0
    cnt = [0, 0, 0]
    ptr = head

    # Traverse and count total number of '0', '1' and '2'
    # cnt[0] will store total number of '0's
    # cnt[1] will store total number of '1's
    # cnt[2] will store total number of '2's
    while ptr is not None:
        cnt[ptr.data] += 1
        ptr = ptr.next

    idx = 0
    ptr = head

    # Fill first cnt[0] nodes with value 0
    # Fill next cnt[1] nodes with value 1
    # Fill remaining cnt[2] nodes with value 2
    while ptr is not None:
        if cnt[idx] == 0:
            idx += 1
        else:
            ptr.data = idx
            cnt[idx] -= 1
            ptr = ptr.next

def print_list(node):
    while node is not None:
        print(f" {node.data}", end='')
        node = node.next
    print("\n")


if __name__ == "__main__":

    # Create a hard-coded linked list:
    # 1 -> 1 -> 2 -> 1 -> 0 -> NULL
    head = Node(1)
    head.next = Node(1)
    head.next.next = Node(2)
    head.next.next.next = Node(1)
    head.next.next.next.next = Node(0)

    print("Linked List before Sorting:", end='')
    print_list(head)
    
    sort_list(head)

    print("Linked List after Sorting:", end='')
    print_list(head)
C# 
// C#  Program to sort a linked list of 0s, 1s or 2s
using System;

class Node {
    public int Data;
    public Node Next;

    public Node(int newData) {
        Data = newData;
        Next = null;
    }
}

class GfG {
  
    // Function to sort a linked list of 0s, 1s, and 2s
    static void SortList(Node head) {
      
        // Initialize count of '0', '1', and '2' as 0
        int[] cnt = { 0, 0, 0 };
        Node ptr = head;

        // Traverse and count total number of '0', '1', and '2'
        // cnt[0] will store total number of '0's
        // cnt[1] will store total number of '1's
        // cnt[2] will store total number of '2's
        while (ptr != null) {
            cnt[ptr.Data] += 1;
            ptr = ptr.Next;
        }

        int idx = 0;
        ptr = head;

        // Fill first cnt[0] nodes with value 0
        // Fill next cnt[1] nodes with value 1
        // Fill remaining cnt[2] nodes with value 2
        while (ptr != null) {
            if (cnt[idx] == 0)
                idx += 1;
            else {
                ptr.Data = idx;
                cnt[idx] -= 1;
                ptr = ptr.Next;
            }
        }
    }

    static void PrintList(Node node) {
        while (node != null) {
            Console.Write(" " + node.Data);
            node = node.Next;
        }
        Console.WriteLine();
    }

    static void Main() {
      
        // Create a hard-coded linked list:
        // 1 -> 1 -> 2 -> 1 -> 0 -> NULL
        Node head = new Node(1);
        head.Next = new Node(1);
        head.Next.Next = new Node(2);
        head.Next.Next.Next = new Node(1);
        head.Next.Next.Next.Next = new Node(0);

        Console.Write("Linked List before Sorting:");
        PrintList(head);

        SortList(head);

        Console.Write("Linked List after Sorting:");
        PrintList(head);
    }
}
JavaScript 
// JavaScript Program to sort a linked list of 0s, 1s or 2s
class Node {
    constructor(newData) {
        this.data = newData;
        this.next = null;
    }
}

// Function to sort a linked list of 0s, 1s and 2s
function sortList(head) {

    // Initialize count of '0', '1' and '2' as 0
    const cnt = [ 0, 0, 0 ];
    let ptr = head;

    // Traverse and count total number of '0', '1' and '2'
    // cnt[0] will store total number of '0's
    // cnt[1] will store total number of '1's
    // cnt[2] will store total number of '2's
    while (ptr !== null) {
        cnt[ptr.data] += 1;
        ptr = ptr.next;
    }

    let idx = 0;
    ptr = head;

    // Fill first cnt[0] nodes with value 0
    // Fill next cnt[1] nodes with value 1
    // Fill remaining cnt[2] nodes with value 2
    while (ptr !== null) {
        if (cnt[idx] === 0) {
            idx += 1;
        }
        else {
            ptr.data = idx;
            cnt[idx] -= 1;
            ptr = ptr.next;
        }
    }
}

function printList(node) {
    while (node !== null) {
        console.log(node.data);
        node = node.next;
    }
    console.log();
}


// Create a hard-coded linked list:
// 1 -> 1 -> 2 -> 1 -> 0 -> NULL
let head = new Node(1);
head.next = new Node(1);
head.next.next = new Node(2);
head.next.next.next = new Node(1);
head.next.next.next.next = new Node(0);

console.log("Linked List before Sorting:");
printList(head);

sortList(head);

console.log("Linked List after Sorting:");
printList(head);

Output
Linked List before Sorting: 1 1 2 1 0
Linked List after Sorting: 0 1 1 1 2

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

[Expected Approach – 2] By Updating 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.

Below is the implementation of the above approach:

C++ 
// C++ Program to sort a linked list 0s, 1s
// or 2s by updating links
#include <bits/stdc++.h>
using namespace std;

class Node {
  public:
    int data;
    Node *next;

    Node(int new_data) {
        data = new_data;
        next = nullptr;
    }
};

// Sort a linked list of 0s, 1s, and 2s by changing pointers
Node *sortList(Node *head) {
    if (!head || !(head->next))
        return head;

    // Create three dummy nodes to point to the beginning of
    // three linked lists. These dummy nodes are created to
    // avoid null checks.
    Node *zeroD = new Node(0);
    Node *oneD = new Node(0);
    Node *twoD = new Node(0);

    // Initialize current pointers for three lists
    Node *zero = zeroD, *one = oneD, *two = twoD;

    // Traverse the list
    Node *curr = head;
    while (curr != NULL) {
        if (curr->data == 0) {
          
            // If the data of the current node is 0,
            // append it to pointer zero and update zero
            zero->next = curr;
            zero = zero->next;
        }
        else if (curr->data == 1) {
          
            // If the data of the current node is 1,
            // append it to pointer one and update one
            one->next = curr;
            one = one->next;
        }
        else {
          
            // If the data of the current node is 2,
            // append it to pointer two and update two
            two->next = curr;
            two = two->next;
        }
        curr = curr->next;
    }

    // Combine the three lists
    if (oneD->next) 
        zero->next = oneD->next;
    else
        zero->next = twoD->next;
  
    one->next = twoD->next;
    two->next = nullptr;

    // Updated head
    head = zeroD->next;
    return head;
}


void printList(Node *node) {
    while (node != nullptr) {
        cout << " " << node->data;
        node = node->next;
    }
    cout << "\n";
}

int main() {
  
    // Create a hard-coded linked list:
    // 1 -> 1 -> 2 -> 1 -> 0 -> NULL
    Node *head = new Node(1);
    head->next = new Node(1);
    head->next->next = new Node(2);
    head->next->next->next = new Node(1);
    head->next->next->next->next = new Node(0);

    cout << "Linked List before Sorting:";
    printList(head);

    head = sortList(head);

    cout << "Linked List after Sorting:";
    printList(head);

    return 0;
}
C 
// C Program to sort a linked list 0s, 1s 
// or 2s by updating links

#include <stdio.h>

struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int new_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 null checks. 
    struct Node* zeroD = createNode(0); 
    struct Node* oneD = createNode(0); 
    struct Node* twoD = createNode(0);

    // Initialize current pointers for three 
    // lists 
    struct Node *zero = zeroD, *one = oneD, *two = twoD; 

    // Traverse list 
    struct Node* curr = head; 
    while (curr) { 
        if (curr->data == 0) { 
          
            // If the data of current node is 0, 
            // append it to pointer zero and update zero
            zero->next = curr; 
            zero = zero->next; 
        } 
        else if (curr->data == 1) { 
          
            // If the data of current node is 1, 
            // append it to pointer one and update one
            one->next = curr; 
            one = one->next; 
        } 
        else { 
          
            // If the data of current node is 2, 
            // append it to pointer two and update two
            two->next = curr; 
            two = two->next; 
        } 
        curr = curr->next; 
    } 

    // Combine the three lists
    zero->next = (oneD->next) ? (oneD->next) : (twoD->next); 
    one->next = twoD->next; 
    two->next = NULL; 
      
    // Updated head 
    head = zeroD->next; 
    return head; 
} 

void printList(struct Node* node) {
    while (node != NULL) {
        printf(" %d", node->data);
        node = node->next;
    }
    printf("\n");
}

struct Node* createNode(int new_data) {
    struct Node* new_node = 
       (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = NULL;
    return new_node;
}

int main() {
  
    // Create a hard-coded linked list:
    // 1 -> 1 -> 2 -> 1 -> 0 -> NULL 
    struct Node* head = createNode(1);
    head->next = createNode(1);
    head->next->next = createNode(2);
    head->next->next->next = createNode(1);
    head->next->next->next->next = createNode(0);

    printf("Linked List before Sorting:");
    printList(head);

    head = sortList(head);

    printf("Linked List after Sorting:");
    printList(head);

    return 0;
}
Java 
// Java Program to sort a linked list of 0s, 1s 
// or 2s by updating links 

class Node {
    int data;
    Node next;

    Node(int new_data) {
        data = new_data;
        next = null;
    }
}
 
class GfG {
  
      // Sort a linked list of 0s, 1s and 2s 
    // by changing pointers
    static Node sortList(Node head) {
        if (head == null || head.next == null) 
            return head; 

        // Create three dummy nodes to point to beginning of 
        // three linked lists. These dummy nodes are created to 
        // avoid null checks. 
        Node zeroD = new Node(0); 
        Node oneD = new Node(0); 
        Node twoD = new Node(0);

        // Initialize current pointers for three 
        // lists 
        Node zero = zeroD, one = oneD, two = twoD; 

        // Traverse list 
        Node curr = head; 
        while (curr != null) { 
            if (curr.data == 0) { 
                  
                // If the data of current node is 0, 
                // append it to pointer zero and update zero
                zero.next = curr; 
                zero = zero.next; 
            } 
            else if (curr.data == 1) { 
                  
                // If the data of current node is 1, 
                // append it to pointer one and update one
                one.next = curr; 
                one = one.next; 
            } 
            else { 
                  
                // If the data of current node is 2, 
                // append it to pointer two and update two
                two.next = curr; 
                two = two.next; 
            } 
            curr = curr.next; 
        } 

        // Combine the three lists
        zero.next = (oneD.next != null) ? (oneD.next) : (twoD.next); 
        one.next = twoD.next; 
        two.next = null; 
          
        // Updated head 
        head = zeroD.next; 

        return head; 
    } 

    static void printList(Node node) {
        while (node != null) {
            System.out.print(" " + node.data);
            node = node.next;
        }
        System.out.println();
    }
  
      public static void main(String[] args) {
      
        // Create a hard-coded linked list:
        // 1 -> 1 -> 2 -> 1 -> 0 -> NULL 
        Node head = new Node(1);
        head.next = new Node(1);
        head.next.next = new Node(2);
        head.next.next.next = new Node(1);
        head.next.next.next.next = new Node(0);

        System.out.print("Linked List before Sorting:");
        printList(head);

        head = sortList(head);

        System.out.print("Linked List after Sorting:");
        printList(head);
    }
}
Python 
# Python Program to sort a linked list 0s, 1s 
# or 2s by updating links 

class Node:
    def __init__(self, new_data):
        self.data = new_data
        self.next = None

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

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

    # Initialize current pointers for three 
    # lists 
    zero = zeroD
    one = oneD
    two = twoD

    # Traverse list 
    curr = head
    while curr:
        if curr.data == 0:
          
            # If the data of current node is 0, 
            # append it to pointer zero and update zero
            zero.next = curr
            zero = zero.next
        elif curr.data == 1:
          
            # If the data of cu
            # append it to pointer one and update one
            one.next = curr
            one = one.next
        else:
            # If the data of current node is 2, 
            # append it to pointer two and update two
            two.next = curr
            two = two.next
        curr = curr.next

    # Combine the three lists
    zero.next = oneD.next if oneD.next else twoD.next
    one.next = twoD.next
    two.next = None

    # Updated head 
    head = zeroD.next

    return head

def printList(node):
    while node is not None:
        print(node.data, end=' ')
        node = node.next
    print()

if __name__ == "__main__":
  
    # Create a hard-coded linked list:
    # 1 -> 1 -> 2 -> 1 -> 0 -> NULL 
    head = Node(1)
    head.next = Node(1)
    head.next.next = Node(2)
    head.next.next.next = Node(1)
    head.next.next.next.next = Node(0)

    print("Linked List before Sorting: ", end='')
    printList(head)

    head = sortList(head)

    print("Linked List after Sorting: ", end='')
    printList(head)
C# 
// C# Program to sort a linked list 0s, 1s 
// or 2s by updating links 
using System;

public class Node {
    public int Data;
    public Node Next;
  
    public Node(int newData) {
        Data = newData;
        Next = null;
    }
}

// Sort a linked list of 0s, 1s and 2s 
// by changing pointers 
class GfG {
    static Node SortList(Node head) {
        if (head == null || head.Next == null)
            return head;

        // Create three dummy nodes to point to beginning of 
        // three linked lists. These dummy nodes are created to 
        // avoid null checks. 
        Node zeroD = new Node(0);
        Node oneD = new Node(0);
        Node twoD = new Node(0);

        // Initialize current pointers for three 
        // lists 
        Node zero = zeroD, one = oneD, two = twoD;

        // Traverse list 
        Node curr = head;
        while (curr != null) {
            if (curr.Data == 0) {
              
                // If the data of current node is 0, 
                // append it to pointer zero and update zero
                zero.Next = curr;
                zero = zero.Next;
            }
            else if (curr.Data == 1) {
              
                // If the data of current node is 1, 
                // append it to pointer one and update one
                one.Next = curr;
                one = one.Next;
            }
            else {
              
                // If the data of current node is 2, 
                // append it to pointer two and update two
                two.Next = curr;
                two = two.Next;
            }
            curr = curr.Next;
        }

        // Combine the three lists
        zero.Next = (oneD.Next != null) ? (oneD.Next) : (twoD.Next);
        one.Next = twoD.Next;
        two.Next = null;

        // Updated head 
        head = zeroD.Next;

        // Delete dummy nodes
        // In C# garbage collection will handle this

        return head;
    }

    // This function prints the contents 
    // of the linked list starting from the head
    static void PrintList(Node node) {
        while (node != null) {
            Console.Write(" " + node.Data);
            node = node.Next;
        }
        Console.WriteLine();
    }
  
  
      static void Main() {
      
        // Create a hard-coded linked list:
        // 1 -> 1 -> 2 -> 1 -> 0 -> NULL 
        Node head = new Node(1);
        head.Next = new Node(1);
        head.Next.Next = new Node(2);
        head.Next.Next.Next = new Node(1);
        head.Next.Next.Next.Next = new Node(0);

        Console.Write("Linked List before Sorting:");
        PrintList(head);

        head = SortList(head);

        Console.Write("Linked List after Sorting:");
        PrintList(head);
    }
}
JavaScript 
// Javascript program to sort a linked list of 0s, 1s
// or 2s by updating links
class Node {
    constructor(newData) {
        this.data = newData;
        this.next = null;
    }
}

// Sort a linked list of 0s, 1s and 2s
// by changing pointers
function sortList(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 null checks.
    let zeroD = new Node(0);
    let oneD = new Node(0);
    let twoD = new Node(0);

    // Initialize current pointers for three
    // lists
    let zero = zeroD, one = oneD, two = twoD;

    // Traverse list
    let curr = head;
    while (curr) {
        if (curr.data === 0) {

            // If the data of current node is 0,
            // append it to pointer zero and update zero
            zero.next = curr;
            zero = zero.next;
        }
        else if (curr.data === 1) {

            // If the data of current node is 1,
            // append it to pointer one and update one
            one.next = curr;
            one = one.next;
        }
        else {

            // If the data of current node is 2,
            // append it to pointer two and update two
            two.next = curr;
            two = two.next;
        }
        curr = curr.next;
    }

    // Combine the three lists
    zero.next = (oneD.next) ? (oneD.next) : (twoD.next);
    one.next = twoD.next;
    two.next = null;

    // Updated head
    head = zeroD.next;

    return head;
}

function printList(node) {
    while (node !== null) {
        console.log(node.data);
        node = node.next;
    }
    console.log();
}

// Create a hard-coded linked list:
// 1 -> 1 -> 2 -> 1 -> 0 -> NULL
let head = new Node(1);
head.next = new Node(1);
head.next.next = new Node(2);
head.next.next.next = new Node(1);
head.next.next.next.next = new Node(0);

console.log("Linked List before Sorting:");
printList(head);

head = sortList(head);

console.log("Linked List after Sorting:");
printList(head);

Output
Linked List before Sorting: 1 1 2 1 0
Linked List after Sorting: 0 1 1 1 2

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



https://media.geeksforgeeks.org/auth/avatar.png
GeeksforGeeks
News
Improve
Previous Article
Sorting Big Integers
Next Article
Count Inversions of an Array

Similar Reads

Sort a K sorted Doubly Linked List | Set 2 (Using Shell Sort)
Given a doubly-linked list containing N nodes, where each node is at most K away from its target position in the list, the task is to sort the given doubly linked list. Examples: Input: DLL: 3<->6<->2<->12<->56<->8, K = 2Output: 2<->3<->6<->8<->12<->56 Input: DLL: 3<->2<->1<
12 min read
Comparison among Bubble Sort, Selection Sort and Insertion Sort
Bubble Sort, Selection Sort, and Insertion Sort are simple sorting algorithms that are commonly used to sort small datasets or as building blocks for more complex sorting algorithms. Here's a comparison of the three algorithms: Bubble Sort:Time complexity: O(n^2) in the worst and average cases, O(n) in the best case (when the input array is already
15 min read
Tag sort or Bucket sort or Bin sort in Python
Tag sort, also known as Bucket sort or Bin sort, is a non-comparison based sorting algorithm that distributes elements of an array into a number of "buckets", and then sorts each bucket individually. Tag sort or Bucket sort or Bin sort Algorithm:Determine Range:Find the maximum and minimum values in the input array to determine the range of tags ne
2 min read
Why Quick Sort preferred for Arrays and Merge Sort for Linked Lists?
Why is Quick Sort preferred for arrays? Below are recursive and iterative implementations of Quick Sort and Merge Sort for arrays. Recursive Quick Sort for array. Iterative Quick Sort for arrays. Recursive Merge Sort for arrays Iterative Merge Sort for arrays Quick Sort in its general form is an in-place sort (i.e. it doesn't require any extra stor
5 min read
Is two way linked list and doubly linked list same?
Yes, a two-way linked list and a doubly linked list are the same. Both terms refer to a type of linked list where each node contains a reference to the next node as well as the previous node in the sequence. The term “two-way” emphasizes the ability to move in both directions through the list, while “doubly” highlights that there are two links per
3 min read
Difference between Singly linked list and Doubly linked list
Introduction to Singly linked list : A singly linked list is a set of nodes where each node has two fields 'data' and 'link'. The 'data' field stores actual piece of information and 'link' field is used to point to next node. Basically the 'link' field stores the address of the next node.  Introduction to Doubly linked list : A Doubly Linked List (
2 min read
Convert Singly Linked List to XOR Linked List
Prerequisite: XOR Linked List – A Memory Efficient Doubly Linked List | Set 1XOR Linked List – A Memory Efficient Doubly Linked List | Set 2 An XOR linked list is a memory efficient doubly linked list in which the next pointer of every node stores the XOR of previous and next node's address. Given a singly linked list, the task is to convert the gi
9 min read
XOR linked list- Remove first node of the linked list
Given an XOR linked list, the task is to remove the first node of the XOR linked list. Examples: Input: XLL = 4 < – > 7 < – > 9 < – > 7 Output: 7 < – > 9 < – > 7 Explanation: Removing the first node of the XOR linked list modifies XLL to 7 < – > 9 < – > 7 Input: XLL = NULL Output: List Is Empty Approach: Th
11 min read
Remove all occurrences of one Linked list in another Linked list
Given two linked lists head1 and head2, the task is to remove all occurrences of head2 in head1 and return the head1. Examples: Input: head1 = 2 -> 3 -> 4 -> 5 -> 3 -> 4, head2 = 3 -> 4Output: 2 -> 5Explanation: After removing all occurrences of 3 -> 4 in head1 output is 2 -> 5. Input: head1 = 3 -> 6 -> 9 -> 8 -
9 min read
Count occurrences of one linked list in another Linked List
Given two linked lists head1 and head2, the task is to find occurrences of head2 in head1. Examples: Input: Head1 = 1->2->3->2->4->5->2->4, Head2 = 2->4Output: Occurrences of head2 in head1: 2 Input: Head1 = 3->4->1->5->2, Head2 = 3->4Output: Occurrences of Head2 in Head1: 1 Approach 1: To solve the problem us
15 min read
When is Doubly Linked List more Efficient than Singly Linked List?
Did you know there are some cases where a Doubly Linked List is more efficient than a Singly Linked List, even though it takes more memory compared to a Singly Linked List? What are those Cases? Well, we will discuss that in the following article, But first, let's talk about Singly and linked lists: What is a Singly Linked List?A singly linked list
4 min read
XOR Linked List - Reverse a Linked List in groups of given size
Given a XOR linked list and an integer K, the task is to reverse every K nodes in the given XOR linked list. Examples: Input: XLL = 7< – > 6 < – > 8 < – > 11 < – > 3, K = 3 Output: 8 < – > 6 < – > 7 < – > 3 < – > 11 Explanation: Reversing first K(= 3) nodes modifies the Linked List to 8 < – > 6
13 min read
XOR Linked List: Remove last node of the Linked List
Given an XOR linked list, the task is to delete the node at the end of the XOR Linked List. Examples: Input: 4<–>7<–>9<–>7Output: 4<–>7<–>9Explanation: Deleting a node from the end modifies the given XOR Linked List to 4<–>7<–>9 Input: 10Output: List is emptyExplanation: After deleting the only node present
15+ min read
XOR Linked List - Pairwise swap elements of a given linked list
Given a XOR linked list, the task is to pairwise swap the elements of the given XOR linked list . Examples: Input: 4 <-> 7 <-> 9 <-> 7Output: 7 <-> 4 <-> 7 <-> 9Explanation:First pair of nodes are swapped to formed the sequence {4, 7} and second pair of nodes are swapped to form the sequence {9, 7}. Input: 1 <
12 min read
XOR linked list: Reverse last K nodes of a Linked List
Given a XOR Linked List and a positive integer K, the task is to reverse the last K nodes in the given XOR linked list. Examples: Input: LL: 7 <–> 6 <–> 8 <–> 11 <–> 3 <–> 1, K = 3Output: 7<–>6<–>8<–>1<–>3<–>11 Input: LL: 7 <–> 6 <–> 8 <–> 11 <–> 3 <–> 1 <–
14 min read
XOR Linked List - A Memory Efficient Doubly Linked List | Set 1
In this post, we're going to talk about how XOR linked lists are used to reduce the memory requirements of doubly-linked lists. We know that each node in a doubly-linked list has two pointer fields which contain the addresses of the previous and next node. On the other hand, each node of the XOR linked list requires only a single pointer field, whi
15+ min read
Linked List of Linked List
Linked list of linke­d list, also known as nested linke­d lists, is a type of Linked List where each main node stores another full linked list. This structure­ beats old, plain linked lists. It gives way more­ flexibility to store and manage comple­x data. In this article we will learn about the basics of Linked List of Linked List, how to create L
9 min read
XOR Linked List – A Memory Efficient Doubly Linked List | Set 2
In the previous post, we discussed how a Doubly Linked can be created using only one space for the address field with every node. In this post, we will discuss the implementation of a memory-efficient doubly linked list. We will mainly discuss the following two simple functions. A function to insert a new node at the beginning.A function to travers
10 min read
Create new linked list from two given linked list with greater element at each node
Given two linked list of the same size, the task is to create a new linked list using those linked lists. The condition is that the greater node among both linked list will be added to the new linked list.Examples: Input: list1 = 5->2->3->8list2 = 1->7->4->5Output: New list = 5->7->4->8Input: list1 = 2->8->9->3li
8 min read
Check if a linked list is Circular Linked List
Given the head of a singly linked list, the task is to find if given linked list is circular or not. A linked list is called circular if its last node points back to its first node. Note: The linked list does not contain any internal loops. Example: Input: LinkedList: 2->4->6->7->5 Output: trueExplanation: As shown in figure the first a
12 min read
Javascript Program To Merge A Linked List Into Another Linked List At Alternate Positions
Given two linked lists, insert nodes of the second list into the first list at alternate positions of the first list. For example, if first list is 5->7->17->13->11 and second is 12->10->2->4->6, the first list should become 5->12->7->10->17->2->13->4->11->6 and second list should become empty. The
3 min read
Insert a linked list into another linked list
Given two linked lists, head1 and head2 of sizes m and n respectively. The task is to remove head1's nodes from the ath node to the bth node and insert head2 in their place. Examples: Input: a = 3, b = 4head1: 10 -> 11 -> 12 -> 13 -> 14 -> 15, head2: 100 -> 101 -> 102 -> 103Output: 10 -> 11 -> 12 -> 100 -> 101 -
10 min read
Convert singly linked list into circular linked list
Given a singly linked list, the task is to convert it into a circular linked list. Examples: Input: head: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULLOutput: Explanation: Singly linked list is converted to circular by pointing last node to head. Input: head: 2 -> 4 -> 6 -> 8 -> 10 -> 12 -> NULLOutput: Explanation: Singly l
11 min read
Merge a linked list into another linked list at alternate positions
Given two singly linked lists, The task is to insert nodes of the second list into the first list at alternate positions of the first list and leave the remaining nodes of the second list if it is longer. Example: Input: head1: 1->2->3 , head2: 4->5->6->7->8Output: head1: 1->4->2->5->3->6 , head2: 7->8 Input: hea
8 min read
Sort a linked list that is sorted alternating ascending and descending orders?
Given a Linked List. The Linked List is in alternating ascending and descending orders. Sort the list efficiently. Example: Input List: 10 -> 40 -> 53 -> 30 -> 67 -> 12 -> 89 -> NULL Output List: 10 -> 12 -> 30 -> 40 -> 53 -> 67 -> 89 -> NULL Input List: 1 -> 4 -> 3 -> 2 -> 5 -> NULL Output L
13 min read
Sort a linked list of 0s, 1s and 2s by changing links
Given a linked list of 0s, 1s and 2s, the task is to sort and print it. Examples: Input: 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> NULL Output: 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2 -> NULL Input: 1 -> 1 -> 2 -> 1 -> 0 -> NULL Output: 0 -> 1 -> 1 -> 1 -> 2 -> NULL Approach: To solve the pro
13 min read
Sort a Linked List of 0s and 1s
Given the singly 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 -> NULL Output: 0 -> 0 -> 1 -> 1 -> 1 -> NULL Input: head = 1 -> 1 -> 0 -> NULL Output: 0 -> 1 -> 1 -> NULL Table of Content [Naive
13 min read
Union and Intersection of two Linked List using Merge Sort
Given two singly Linked Lists, create union and intersection lists that contain the union and intersection of the elements present in the given lists. Each of the two lists contains distinct node values. Note: The order of elements in output lists doesn't matter. Examples: Input: head1: 10 -> 15 -> 4 -> 20head2: 8 -> 4 -> 2 -> 10O
15+ min read
Sort the linked list in the order of elements appearing in the array
Given an array of size N and a Linked List where elements will be from the array but can also be duplicated, sort the linked list in the order, elements are appearing in the array. It may be assumed that the array covers all elements of the linked list.arr[] = list = Sorted list = Asked in Amazon First, make a hash table that stores the frequencies
9 min read
Sort the biotonic doubly linked list | Set-2
Sort the given biotonic doubly linked list. A biotonic doubly linked list is a doubly-linked list which is first increasing and then decreasing. A strictly increasing or a strictly decreasing list is also a biotonic doubly linked list. Examples: Input : 2 5 7 12 10 6 4 1 Output : 1 2 4 5 6 7 10 12 Input : 20 17 14 8 3 Output : 3 8 14 17 20Recommend
15 min read
Article Tags :
Practice Tags :
three90RightbarBannerImg
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox