Sorting a Singly Linked List

Last Updated : 21 Jun, 2024

Given a Linked List, the task is to sort this Linked List in ascending order.

sorting image

Examples:

Input: 10->30->20->5
Output: 5->10->20->30

Input: 20->4->3
Output: 3->4->20

Approach: We can sort the LinkedList by many sorting techniques:

Method 1: Sort Linked List using Bubble Sort

Get the Linked List to be sorted
Apply Bubble Sort to this linked list, in which, while comparing the two adjacent nodes, actual nodes are swapped instead of just swapping the data.
Print the sorted list

Below is the implementation of the above approach:

C++

// C++ program to sort Linked List
// using Bubble Sort
// by swapping nodes

#include <iostream>
using namespace std;

/* structure for a node */
struct Node {
    int data;
    struct Node* next;
} Node;

/*Function to swap the nodes */
struct Node* swap(struct Node* ptr1, struct Node* ptr2)
{
    struct Node* tmp = ptr2->next;
    ptr2->next = ptr1;
    ptr1->next = tmp;
    return ptr2;
}

/* Function to sort the list */
void bubbleSort(struct Node** head, int count)
{
    struct Node** h;
    int i, j, swapped;

    for (i = 0; i < count; i++) {

        h = head;
        swapped = 0;

        for (j = 0; j < count - i - 1; j++) {

            struct Node* p1 = *h;
            struct Node* p2 = p1->next;

            if (p1->data > p2->data) {

                /* update the link after swapping */
                *h = swap(p1, p2);
                swapped = 1;
            }

            h = &(*h)->next;
        }

        /* break if the loop ended without any swap */
        if (swapped == 0)
            break;
    }
}

/* Function to print the list */
void printList(struct Node* n)
{
    while (n != NULL) {
        cout << n->data << " -> ";
        n = n->next;
    }
    cout << endl;
}

/* Function to insert a struct Node
at the beginning of a linked list */
void insertAtTheBegin(struct Node** start_ref, int data)
{
    struct Node* ptr1
        = (struct Node*)malloc(sizeof(struct Node));

    ptr1->data = data;
    ptr1->next = *start_ref;
    *start_ref = ptr1;
}

// Driver Code
int main()
{
    int arr[] = { 78, 20, 10, 32, 1, 5 };
    int list_size, i;

    /* start with empty linked list */
    struct Node* start = NULL;
    list_size = sizeof(arr) / sizeof(arr[0]);

    /* Create linked list from the array arr[] */
    for (i = list_size - 1; i >= 0; i--)
        insertAtTheBegin(&start, arr[i]);

    /* print list before sorting */
    cout << "Linked list before sorting\n";
    printList(start);

    /* sort the linked list */
    bubbleSort(&start, list_size);

    /* print list after sorting */
    cout << "Linked list after sorting\n";
    printList(start);

    return 0;
}

// C program to sort Linked List
// using Bubble Sort
// by swapping nodes

#include <stdio.h>
#include <stdlib.h>

/* structure for a node */
struct Node {
    int data;
    struct Node* next;
} Node;

/*Function to swap the nodes */
struct Node* swap(struct Node* ptr1, struct Node* ptr2)
{
    struct Node* tmp = ptr2->next;
    ptr2->next = ptr1;
    ptr1->next = tmp;
    return ptr2;
}

/* Function to sort the list */
int bubbleSort(struct Node** head, int count)
{
    struct Node** h;
    int i, j, swapped;

    for (i = 0; i <= count; i++) {

        h = head;
        swapped = 0;

        for (j = 0; j < count - i - 1; j++) {

            struct Node* p1 = *h;
            struct Node* p2 = p1->next;

            if (p1->data > p2->data) {

                /* update the link after swapping */
                *h = swap(p1, p2);
                swapped = 1;
            }

            h = &(*h)->next;
        }

        /* break if the loop ended without any swap */
        if (swapped == 0)
            break;
    }
}

/* Function to print the list */
void printList(struct Node* n)
{
    while (n != NULL) {
        printf("%d -> ", n->data);
        n = n->next;
    }
    printf("\n");
}

/* Function to insert a struct Node
at the beginning of a linked list */
void insertAtTheBegin(struct Node** start_ref, int data)
{
    struct Node* ptr1
        = (struct Node*)malloc(sizeof(struct Node));

    ptr1->data = data;
    ptr1->next = *start_ref;
    *start_ref = ptr1;
}

// Driver Code
int main()
{
    int arr[] = { 78, 20, 10, 32, 1, 5 };
    int list_size, i;

    /* start with empty linked list */
    struct Node* start = NULL;
    list_size = sizeof(arr) / sizeof(arr[0]);

    /* Create linked list from the array arr[] */
    for (i = list_size - 1; i >= 0; i--)
        insertAtTheBegin(&start, arr[i]);

    /* print list before sorting */
    printf("Linked list before sorting\n");
    printList(start);

    /* sort the linked list */
    bubbleSort(&start, list_size);

    /* print list after sorting */
    printf("Linked list after sorting\n");
    printList(start);

    return 0;
}

Java

// Node class
class Node {
    int data;
    Node next;

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

public class Main {

    // Function to swap the nodes
    static void swap(Node ptr1, Node ptr2) {
        int tmp = ptr2.data;
        ptr2.data = ptr1.data;
        ptr1.data = tmp;
    }

    // Function to sort the list
    static void bubbleSort(Node head) {
        boolean swapped;
        Node current;

        if (head == null)
            return;

        do {
            swapped = false;
            current = head;

            while (current.next != null) {
                if (current.data > current.next.data) {
                    swap(current, current.next);
                    swapped = true;
                }
                current = current.next;
            }
        } while (swapped);
    }

    // Function to print the list
    static void printList(Node n) {
        while (n != null) {
            System.out.print(n.data + " -> ");
            n = n.next;
        }
        System.out.println();
    }

    // Function to insert a Node at the beginning of a linked list
    static Node insertAtTheBegin(Node start_ref, int data) {
        Node ptr1 = new Node(data);

        ptr1.next = start_ref;
        start_ref = ptr1;
        return start_ref; // Return the updated start_ref
    }

    // Driver Code
    public static void main(String[] args) {
        int[] arr = { 78, 20, 10, 32, 1, 5 };
        int listSize = arr.length;

        Node start = null;

        // Create linked list from the array arr[]
        for (int i = listSize - 1; i >= 0; i--)
            start = insertAtTheBegin(start, arr[i]);

        System.out.println("Linked list before sorting");
        printList(start);

        bubbleSort(start);

        System.out.println("Linked list after sorting");
        printList(start);
    }
}

Python

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

def swap(ptr1, ptr2):
    tmp = ptr2.data
    ptr2.data = ptr1.data
    ptr1.data = tmp

def bubbleSort(head):
    swapped = True

    while swapped:
        swapped = False
        current = head

        while current.next:
            if current.data > current.next.data:
                swap(current, current.next)
                swapped = True
            current = current.next

def printList(n):
    while n:
        print(n.data, "->", end=" ")
        n = n.next
    print()

def insertAtTheBegin(start_ref, data):
    ptr1 = Node(data)
    ptr1.next = start_ref
    return ptr1

# Driver Code
if __name__ == "__main__":
    arr = [0,1,0,1,0,1]
    list_size = len(arr)

    start = None

    # Create linked list from the array arr[]
    for i in range(list_size - 1, -1, -1):
        start = insertAtTheBegin(start, arr[i])

    print("Linked list before sorting")
    printList(start)

    bubbleSort(start)

    print("Linked list after sorting")
    printList(start)

// C# program to sort Linked List
// using Bubble Sort
// by swapping nodes

using System;

// Node class
class Node
{
    public int data;
    public Node next;

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

class MainClass
{
     // Function to swap the nodes
    static void swap(Node ptr1, Node ptr2)
    {
        int tmp = ptr2.data;
        ptr2.data = ptr1.data;
        ptr1.data = tmp;
    }

    // Function to sort the list
    static void bubbleSort(Node head)
    {
        bool swapped;
        Node current;

        if (head == null)
            return;

        do
        {
            swapped = false;
            current = head;

            while (current.next != null)
            {
                if (current.data > current.next.data)
                {
                    swap(current, current.next);
                    swapped = true;
                }
                current = current.next;
            }
        } while (swapped);
    }
    
     // Function to print the list
    static void printList(Node n)
    {
        while (n != null)
        {
            Console.Write(n.data + " -> ");
            n = n.next;
        }
        Console.WriteLine();
    }
    
    // Function to insert a Node at the beginning of a linked list
    static Node insertAtTheBegin(Node start_ref, int data)
    {
        Node ptr1 = new Node(data);
        ptr1.next = start_ref;
        start_ref = ptr1;
        // Return the updated start_ref
        return start_ref;
    }
    
    // Driver Code
    public static void Main(string[] args)
    {
        int[] arr = { 78, 20, 10, 32, 1, 5 };
        int listSize = arr.Length;

        Node start = null;
        
        // Create linked list from the array arr[]
        for (int i = listSize - 1; i >= 0; i--)
        {
            start = insertAtTheBegin(start, arr[i]);
        }

        Console.WriteLine("Linked list before sorting:");
        printList(start);

        bubbleSort(start);

        Console.WriteLine("Linked list after sorting:");
        printList(start);
    }
}

// This code is contributed by Pushpesh raj

Javascript

// Javascript program to sort Linked List
// using Bubble Sort
// by swapping nodes

// Node class
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

// Function to swap the nodes
function swap(ptr1, ptr2) {
  let tmp = ptr2.data;
  ptr2.data = ptr1.data;
  ptr1.data = tmp;
}

// Function to sort the list
function bubbleSort(head) {
  let i, j;
  let swapped;

  if (head == null)
    return;

  do {
    swapped = false;
    let current = head;

    while (current.next != null) {
      if (current.data > current.next.data) {
        swap(current, current.next);
        swapped = true;
      }
      current = current.next;
    }
  } while (swapped);
}

// Function to print the list
function printList(n) {
  while (n != null) {
    console.log(n.data + " -> ");
    n = n.next;
  }
  console.log();
}

// Function to insert a Node at the beginning of a linked list
function insertAtTheBegin(start_ref, data) {
  let ptr1 = new Node(data);

  ptr1.next = start_ref;
  start_ref = ptr1;
  return start_ref; // Return the updated start_ref
}

// Driver Code
function main() {
  let arr = [78, 20, 10, 32, 1, 5];
  let list_size, i;

  let start = null;
  list_size = arr.length;

  // Create linked list from the array arr[]
  for (i = list_size - 1; i >= 0; i--)
    start = insertAtTheBegin(start, arr[i]);

  console.log("Linked list before sorting");
  printList(start);

  bubbleSort(start);

  console.log("Linked list after sorting");
  printList(start);
}

main();

Output

Linked list before sorting
78 -> 20 -> 10 -> 32 -> 1 -> 5 -> 
Linked list after sorting
1 -> 5 -> 10 -> 20 -> 32 -> 78 ->

Time complexity: O(n ^ 2)
Auxiliary Space: O(1)

Method 2: Sort Linked List using Insertion Sort

Below is a simple insertion sort algorithm for a linked list.

Create an empty sorted (or result) list
Traverse the given list, do following for every node.
- Insert current node in sorted way in sorted or result list.
Change head of given linked list to head of sorted (or result) list.

Below is the implementation of the above approach:

C++

// C++ program to sort link list
// using insertion sort
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    struct Node* next;
    Node(int x)
    {
        val = x;
        next = NULL;
    }
};

class LinkedlistIS {

public:
    Node* head;
    Node* sorted;

    void push(int val)
    {
        /* allocate node */
        Node* newnode = new Node(val);
        /* link the old list of the new node */
        newnode->next = head;
        /* move the head to point to the new node */
        head = newnode;
    }

    // function to sort a singly linked list using insertion
    // sort
    void insertionSort(Node* headref)
    {
        // Initialize sorted linked list
        sorted = NULL;
        Node* current = headref;
        // Traverse the given linked list and insert every
        // node to sorted
        while (current != NULL) {
            // Store next for next iteration
            Node* next = current->next;
            // insert current in sorted linked list
            sortedInsert(current);
            // Update current
            current = next;
        }
        // Update head_ref to point to sorted linked list
        head = sorted;
    }

    /*
     * function to insert a new_node in a list. Note that
     * this function expects a pointer to head_ref as this
     * can modify the head of the input linked list
     * (similar to push())
     */
    void sortedInsert(Node* newnode)
    {
        /* Special case for the head end */
        if (sorted == NULL || sorted->val >= newnode->val) {
            newnode->next = sorted;
            sorted = newnode;
        }
        else {
            Node* current = sorted;
            /* Locate the node before the point of insertion
             */
            while (current->next != NULL
                   && current->next->val < newnode->val) {
                current = current->next;
            }
            newnode->next = current->next;
            current->next = newnode;
        }
    }
    /* Function to print linked list */
    void printlist(Node* head)
    {
        while (head != NULL) {
            cout << head->val << " ";
            head = head->next;
        }
    }
};
// Driver program to test above functions
int main()
{
    LinkedlistIS list;
    list.head = NULL;
    list.push(5);
    list.push(20);
    list.push(4);
    list.push(3);
    list.push(30);
    cout << "Linked List before sorting" << endl;
    list.printlist(list.head);
    cout << endl;
    list.insertionSort(list.head);
    cout << "Linked List After sorting" << endl;
    list.printlist(list.head);
}

// C program to sort link list
// using insertion sort
#include <stdio.h>
#include <stdlib.h>

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

struct node* head = NULL;
struct node* sorted = NULL;

void push(int val)
{
    /* allocate node */
    struct node* newnode
        = (struct node*)malloc(sizeof(struct node));
    newnode->data = val;
    /* link the old list of the new node */
    newnode->next = head;
    /* move the head to point to the new node */
    head = newnode;
}

/*
 * function to insert a new_node in a list. Note that
 * this function expects a pointer to head_ref as this
 * can modify the head of the input linked list
 * (similar to push())
 */
void sortedInsert(struct node* newnode)
{
    /* Special case for the head end */
    if (sorted == NULL || sorted->data >= newnode->data) {
        newnode->next = sorted;
        sorted = newnode;
    }
    else {
        struct node* current = sorted;
        /* Locate the node before the point of insertion
         */
        while (current->next != NULL
               && current->next->data < newnode->data) {
            current = current->next;
        }
        newnode->next = current->next;
        current->next = newnode;
    }
}

// function to sort a singly linked list
// using insertion sort
void insertionsort()
{

    struct node* current = head;

    // Traverse the given linked list and insert every
    // node to sorted
    while (current != NULL) {

        // Store next for next iteration
        struct node* next = current->next;

        // insert current in sorted linked list
        sortedInsert(current);

        // Update current
        current = next;
    }
    // Update head to point to sorted linked list
    head = sorted;
}

/* Function to print linked list */
void printlist(struct node* head)
{
    while (head != NULL) {
        printf("%d->", head->data);
        head = head->next;
    }
    printf("NULL");
}

// Driver program to test above functions
int main()
{

    push(5);
    push(20);
    push(4);
    push(3);
    push(30);

    printf("Linked List before sorting:\n");
    printlist(head);
    printf("\n");

    insertionsort(head);

    printf("Linked List after sorting:\n");
    printlist(head);
}

Java

public class LinkedlistIS {

    static class Node {
        int val;
        Node next;
        Node(int x)
        {
            val = x;
            next = null;
        }
    };

    Node head;
    Node sorted;

    void push(int val)
    {
        /* allocate node */
        Node newnode = new Node(val);
        /* link the old list of the new node */
        newnode.next = head;
        /* move the head to point to the new node */
        head = newnode;
    }

    // function to sort a singly linked list using insertion
    // sort
    void insertionSort(Node headref)
    {
        // Initialize sorted linked list
        sorted = null;
        Node current = headref;
        // Traverse the given linked list and insert every
        // node to sorted
        while (current != null) {
            // Store next for next iteration
            Node next = current.next;
            // insert current in sorted linked list
            sortedInsert(current);
            // Update current
            current = next;
        }
        // Update head_ref to point to sorted linked list
        head = sorted;
    }

    /*
     * function to insert a new_node in a list. Note that
     * this function expects a pointer to head_ref as this
     * can modify the head of the input linked list
     * (similar to push())
     */
    void sortedInsert(Node newnode)
    {
        /* Special case for the head end */
        if (sorted == null || sorted.val >= newnode.val) {
            newnode.next = sorted;
            sorted = newnode;
        }
        else {
            Node current = sorted;
            /* Locate the node before the point of insertion
             */
            while (current.next != null
                   && current.next.val < newnode.val) {
                current = current.next;
            }
            newnode.next = current.next;
            current.next = newnode;
        }
    }
    /* Function to print linked list */
    void printlist(Node head)
    {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }

    // Driver program to test above functions
    public static void main(String args[])
    {
        LinkedlistIS list = new LinkedlistIS();
        list.head = null;
        list.push(5);
        list.push(20);
        list.push(4);
        list.push(3);
        list.push(30);
        System.out.println("Linked List before sorting");
        list.printlist(list.head);
        System.out.println();
        list.insertionSort(list.head);
        System.out.println("Linked List After sorting");
        list.printlist(list.head);
    }
}

Python

# Python implementation of above algorithm

# Node class


class Node:

    # Constructor to initialize the node object
    def __init__(self, data):
        self.data = data
        self.next = None

# function to sort a singly linked list using insertion sort


def insertionSort(head_ref):

    # Initialize sorted linked list
    sorted = None

    # Traverse the given linked list and insert every
    # node to sorted
    current = head_ref
    while (current != None):

        # Store next for next iteration
        next = current.next

        # insert current in sorted linked list
        sorted = sortedInsert(sorted, current)

        # Update current
        current = next

    # Update head_ref to point to sorted linked list
    head_ref = sorted
    return head_ref

# function to insert a new_node in a list. Note that this
# function expects a pointer to head_ref as this can modify the
# head of the input linked list (similar to push())


def sortedInsert(head_ref, new_node):

    current = None

    # Special case for the head end */
    if (head_ref == None or (head_ref).data >= new_node.data):

        new_node.next = head_ref
        head_ref = new_node

    else:

        # Locate the node before the point of insertion
        current = head_ref
        while (current.next != None and
                current.next.data < new_node.data):

            current = current.next

        new_node.next = current.next
        current.next = new_node

    return head_ref

# BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert

# Function to print linked list */


def printList(head):

    temp = head
    while(temp != None):

        print(temp.data, end=" ")
        temp = temp.next

# A utility function to insert a node
# at the beginning of linked list


def push(head_ref, new_data):

    # allocate node
    new_node = Node(0)

    # 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 program to test above functions


a = None
a = push(a, 5)
a = push(a, 20)
a = push(a, 4)
a = push(a, 3)
a = push(a, 30)

print("Linked List before sorting ")
printList(a)

a = insertionSort(a)

print("\nLinked List after sorting ")
printList(a)

using System;

public class Node
{
    public int val;
    public Node next;

    public Node(int x)
    {
        val = x;
        next = null;
    }
}

public class LinkedListIS
{
    public Node head;
    public Node sorted;

    public void Push(int val)
    {
        // Allocate a new node
        Node newNode = new Node(val);
        // Link the old list to the new node
        newNode.next = head;
        // Move the head to point to the new node
        head = newNode;
    }

    // Function to sort a singly linked list using insertion sort
    public void InsertionSort(Node headRef)
    {
        // Initialize sorted linked list
        sorted = null;
        Node current = headRef;

        // Traverse the given linked list and insert every node into the sorted list
        while (current != null)
        {
            // Store the next node for the next iteration
            Node next = current.next;
            // Insert the current node into the sorted linked list
            SortedInsert(current);
            // Update current to the next node
            current = next;
        }

        // Update the head reference to point to the sorted linked list
        head = sorted;
    }

    // Function to insert a new node in a list
    public void SortedInsert(Node newNode)
    {
        // Special case for the head end
        if (sorted == null || sorted.val >= newNode.val)
        {
            newNode.next = sorted;
            sorted = newNode;
        }
        else
        {
            Node current = sorted;
            // Locate the node before the point of insertion
            while (current.next != null && current.next.val < newNode.val)
            {
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;
        }
    }

    // Function to print the linked list
    public void PrintList(Node current)
    {
        while (current != null)
        {
            Console.Write(current.val + " ");
            current = current.next;
        }
    }
}

class Program
{
    public static void Main()
    {
        LinkedListIS list = new LinkedListIS();
        list.head = null;
        list.Push(5);
        list.Push(20);
        list.Push(4);
        list.Push(3);
        list.Push(30);
        Console.WriteLine("Linked List before sorting");
        list.PrintList(list.head);
        Console.WriteLine();
        list.InsertionSort(list.head);
        Console.WriteLine("Linked List After sorting");
        list.PrintList(list.head);
    }
}

Javascript

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class LinkedlistIS {
  constructor() {
    this.head = null;
    this.sorted = null;
  }

  push(val) {
    // allocate node
    const newnode = new Node(val);
    // link the old list of the new node
    newnode.next = this.head;
    // move the head to point to the new node
    this.head = newnode;
  }

  // function to sort a singly linked list using insertion sort
  insertionSort(headref) {
    // Initialize sorted linked list
    this.sorted = null;
    let current = headref;
    // Traverse the given linked list and insert every
    // node to sorted
    while (current !== null) {
      // Store next for next iteration
      const next = current.next;
      // insert current in sorted linked list
      this.sortedInsert(current);
      // Update current
      current = next;
    }
    // Update head_ref to point to sorted linked list
    this.head = this.sorted;
  }

  /*
   * function to insert a new_node in a list. Note that
   * this function expects a pointer to head_ref as this
   * can modify the head of the input linked list
   * (similar to push())
   */
  sortedInsert(newnode) {
    /* Special case for the head end */
    if (this.sorted === null || this.sorted.val >= newnode.val) {
      newnode.next = this.sorted;
      this.sorted = newnode;
    } else {
      let current = this.sorted;
      /* Locate the node before the point of insertion */
      while (current.next !== null && current.next.val < newnode.val) {
        current = current.next;
      }
      newnode.next = current.next;
      current.next = newnode;
    }
  }

  /* Function to print linked list */
  printlist(head) {
    while (head !== null) {
      console.log(head.val + ' ');
      head = head.next;
    }
  }
}

// Driver program to test above functions
const list = new LinkedlistIS();
list.head = null;
list.push(5);
list.push(20);
list.push(4);
list.push(3);
list.push(30);
console.log('Linked List before sorting');
list.printlist(list.head);
console.log('');
list.insertionSort(list.head);
console.log('Linked List After sorting');
list.printlist(list.head);

Output

Linked List before sorting
30 3 4 20 5 
Linked List After sorting
3 4 5 20 30

Time complexity: O(n ^ 2)
Auxiliary Space: O(1)

Method 3: Sort Linked List using Quick Sort

Call the partition function to get a pivot node placed at its correct position
- In the partition function, the last element is considered a pivot
- Then traverse the current list and if a node has a value greater than the pivot, then move it after the tail. If the node has a smaller value, then keep it at its current position.
- Return pivot node
Find the tail node of the list which is on the left side of the pivot and recur for the left list
Similarly, after the left side, recur for the list on the right side of the pivot
Now return the head of the linked list after joining the left and the right list, as the whole linked list is now sorted

Below is the implementation of the above approach:

C++

// C++ program for Quick Sort on Singly Linked List

#include <cstdio>
#include <iostream>
using namespace std;

/* a node of the singly linked list */
struct Node {
    int data;
    struct Node* next;
};

/* A utility function to insert a node at the beginning of
 * linked list */
void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct 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;
}

/* A utility function to print linked list */
void printList(struct Node* node)
{
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

// Returns the last node of the list
struct Node* getTail(struct Node* cur)
{
    while (cur != NULL && cur->next != NULL)
        cur = cur->next;
    return cur;
}

// Partitions the list taking the last element as the pivot
struct Node* partition(struct Node* head, struct Node* end,
                       struct Node** newHead,
                       struct Node** newEnd)
{
    struct Node* pivot = end;
    struct Node *prev = NULL, *cur = head, *tail = pivot;

    // During partition, both the head and end of the list
    // might change which is updated in the newHead and
    // newEnd variables
    while (cur != pivot) {
        if (cur->data < pivot->data) {
            // First node that has a value less than the
            // pivot - becomes the new head
            if ((*newHead) == NULL)
                (*newHead) = cur;

            prev = cur;
            cur = cur->next;
        }
        else // If cur node is greater than pivot
        {
            // Move cur node to next of tail, and change
            // tail
            if (prev)
                prev->next = cur->next;
            struct Node* tmp = cur->next;
            cur->next = NULL;
            tail->next = cur;
            tail = cur;
            cur = tmp;
        }
    }

    // If the pivot data is the smallest element in the
    // current list, pivot becomes the head
    if ((*newHead) == NULL)
        (*newHead) = pivot;

    // Update newEnd to the current last node
    (*newEnd) = tail;

    // Return the pivot node
    return pivot;
}

// here the sorting happens exclusive of the end node
struct Node* quickSortRecur(struct Node* head,
                            struct Node* end)
{
    // base condition
    if (!head || head == end)
        return head;

    Node *newHead = NULL, *newEnd = NULL;

    // Partition the list, newHead and newEnd will be
    // updated by the partition function
    struct Node* pivot
        = partition(head, end, &newHead, &newEnd);

    // If pivot is the smallest element - no need to recur
    // for the left part.
    if (newHead != pivot) {
        // Set the node before the pivot node as NULL
        struct Node* tmp = newHead;
        while (tmp->next != pivot)
            tmp = tmp->next;
        tmp->next = NULL;

        // Recur for the list before pivot
        newHead = quickSortRecur(newHead, tmp);

        // Change next of last node of the left half to
        // pivot
        tmp = getTail(newHead);
        tmp->next = pivot;
    }

    // Recur for the list after the pivot element
    pivot->next = quickSortRecur(pivot->next, newEnd);

    return newHead;
}

// The main function for quick sort. This is a wrapper over
// recursive function quickSortRecur()
void quickSort(struct Node** headRef)
{
    (*headRef)
        = quickSortRecur(*headRef, getTail(*headRef));
    return;
}

// Driver's code
int main()
{
    struct Node* a = NULL;
    push(&a, 5);
    push(&a, 20);
    push(&a, 4);
    push(&a, 3);
    push(&a, 30);

    cout << "Linked List before sorting \n";
    printList(a);

    // Function call
    quickSort(&a);

    cout << "Linked List after sorting \n";
    printList(a);

    return 0;
}

#include <stdio.h>
#include <stdlib.h>

// Creating structure
struct Node {
    int data;
    struct Node* next;
};

// Add new node at end of linked list
void insert(struct Node** head, int value)
{
    // Create dynamic node
    struct Node* node
        = (struct Node*)malloc(sizeof(struct Node));
    if (node == NULL) {
        // checking memory overflow
        printf("Memory overflow\n");
    }
    else {
        node->data = value;
        node->next = NULL;
        if (*head == NULL) {
            *head = node;
        }
        else {
            struct Node* temp = *head;

            // finding last node
            while (temp->next != NULL) {
                temp = temp->next;
            }

            // adding node at last position
            temp->next = node;
        }
    }
}

// Displaying linked list element
void display(struct Node* head)
{
    if (head == NULL) {
        printf("Empty linked list");
        return;
    }
    struct Node* temp = head;
    printf("\n Linked List :");
    while (temp != NULL) {
        printf(" %d", temp->data);
        temp = temp->next;
    }
}

// Finding last node of linked list
struct Node* last_node(struct Node* head)
{
    struct Node* temp = head;
    while (temp != NULL && temp->next != NULL) {
        temp = temp->next;
    }
    return temp;
}

// We are Setting the given last node position to its proper
// position
struct Node* partition(struct Node* first,
                       struct Node* last)
{
    // Get first node of given linked list
    struct Node* pivot = first;
    struct Node* front = first;
    int temp = 0;
    while (front != NULL && front != last) {
        if (front->data < last->data) {
            pivot = first;

            // Swapping node values
            temp = first->data;
            first->data = front->data;
            front->data = temp;

            // Visiting the next node
            first = first->next;
        }

        // Visiting the next node
        front = front->next;
    }

    // Change last node value to current node
    temp = first->data;
    first->data = last->data;
    last->data = temp;
    return pivot;
}

// Performing quick sort in the given linked list
void quick_sort(struct Node* first, struct Node* last)
{
    if (first == last) {
        return;
    }
    struct Node* pivot = partition(first, last);

    if (pivot != NULL && pivot->next != NULL) {
        quick_sort(pivot->next, last);
    }

    if (pivot != NULL && first != pivot) {
        quick_sort(first, pivot);
    }
}

// Driver's code
int main()
{
    struct Node* head = NULL;

    // Create linked list
    insert(&head, 15);
    insert(&head, 10);
    insert(&head, 5);
    insert(&head, 20);
    insert(&head, 3);
    insert(&head, 2);
    printf("\n Before Sort ");
    display(head);

    // Function call
    quick_sort(head, last_node(head));
    printf("\n After Sort ");
    display(head);
    return 0;
}

Java

class Node {
    int data;
    Node next;

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

public class Main {
    // Function to insert a node at the beginning of the linked list
    public static Node push(Node head, int new_data) {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
        return head;
    }

    // Function to print the linked list
    public static void printList(Node node) {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
        System.out.println();
    }

    // Function to get the last node of the list
    public static Node getTail(Node cur) {
        while (cur != null && cur.next != null)
            cur = cur.next;
        return cur;
    }

    // Function to partition the list, taking the last element as the pivot
    public static Node partition(Node head, Node end, Node[] newHead, Node[] newEnd) {
        Node pivot = end;
        Node prev = null, cur = head, tail = pivot;

        while (cur != pivot) {
            if (cur.data < pivot.data) {
                if (newHead[0] == null)
                    newHead[0] = cur;

                prev = cur;
                cur = cur.next;
            } else {
                if (prev != null)
                    prev.next = cur.next;
                Node tmp = cur.next;
                cur.next = null;
                tail.next = cur;
                tail = cur;
                cur = tmp;
            }
        }

        if (newHead[0] == null)
            newHead[0] = pivot;

        newEnd[0] = tail;

        return pivot;
    }

    // Recursive function for quick sort
    public static Node quickSortRecur(Node head, Node end) {
        if (head == null || head == end)
            return head;

        Node[] newHead = new Node[1];
        Node[] newEnd = new Node[1];

        Node pivot = partition(head, end, newHead, newEnd);

        if (newHead[0] != pivot) {
            Node tmp = newHead[0];
            while (tmp.next != pivot)
                tmp = tmp.next;
            tmp.next = null;

            newHead[0] = quickSortRecur(newHead[0], tmp);
            tmp = getTail(newHead[0]);
            tmp.next = pivot;
        }

        pivot.next = quickSortRecur(pivot.next, newEnd[0]);

        return newHead[0];
    }

    // Wrapper function for quick sort
    public static Node quickSort(Node head) {
        head = quickSortRecur(head, getTail(head));
        return head;
    }

    public static void main(String[] args) {
        Node a = null;
        a = push(a, 5);
        a = push(a, 20);
        a = push(a, 4);
        a = push(a, 3);
        a = push(a, 30);

        System.out.println("Linked List before sorting:");
        printList(a);

        a = quickSort(a);

        System.out.println("Linked List after sorting:");
        printList(a);
    }
}

Python

'''

sort a linked list using quick sort

'''


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


class QuickSortLinkedList:

    def __init__(self):
        self.head = None

    def addNode(self, data):
        if (self.head == None):
            self.head = Node(data)
            return

        curr = self.head
        while (curr.next != None):
            curr = curr.next

        newNode = Node(data)
        curr.next = newNode

    def printList(self, n):
        while (n != None):
            print(n.data, end=" ")
            n = n.next

    ''' takes first and last node,but do not
    break any links in the whole linked list'''

    def partitionLast(self, start, end):
        if (start == end or start == None or end == None):
            return start

        pivot_prev = start
        curr = start
        pivot = end.data

        '''iterate till one before the end,
        no need to iterate till the end because end is pivot'''

        while (start != end):
            if (start.data < pivot):

                # keep tracks of last modified item
                pivot_prev = curr
                temp = curr.data
                curr.data = start.data
                start.data = temp
                curr = curr.next
            start = start.next

        '''swap the position of curr i.e.
        next suitable index and pivot'''

        temp = curr.data
        curr.data = pivot
        end.data = temp

        ''' return one previous to current because
        current is now pointing to pivot '''
        return pivot_prev

    def sort(self, start, end):
        if(start == None or start == end or start == end.next):
            return

        # split list and partition recurse
        pivot_prev = self.partitionLast(start, end)
        self.sort(start, pivot_prev)

        '''
        if pivot is picked and moved to the start,
        that means start and pivot is same
        so pick from next of pivot
        '''
        if(pivot_prev != None and pivot_prev == start):
            self.sort(pivot_prev.next, end)

        # if pivot is in between of the list,start from next of pivot,
        # since we have pivot_prev, so we move two nodes
        elif (pivot_prev != None and pivot_prev.next != None):
            self.sort(pivot_prev.next.next, end)


if __name__ == "__main__":
    ll = QuickSortLinkedList()
    ll.addNode(30)
    ll.addNode(3)
    ll.addNode(4)
    ll.addNode(20)
    ll.addNode(5)

    N = ll.head
    while (N.next != None):
        N = N.next

    print("\nLinked List before sorting")
    ll.printList(ll.head)

    # Function call
    ll.sort(ll.head, N)

    print("\nLinked List after sorting")
    ll.printList(ll.head)

using System;

class Program
{
    // A node of the singly linked list
    class Node
    {
        public int Data;
        public Node Next;
        public Node(int data)
        {
            Data = data;
            Next = null;
        }
    }
    // A utility function to insert a node at 
  // the beginning of the linked list
    static Node Push(Node head, int newData)
    {
        Node newNode = new Node(newData);
        newNode.Next = head;
        return newNode;
    }
    // A utility function to 
  // print the linked list
    static void PrintList(Node node)
    {
        while (node != null)
        {
            Console.Write(node.Data + " ");
            node = node.Next;
        }
        Console.WriteLine();
    }
    // Returns the last node of the list
    static Node GetTail(Node cur)
    {
        while (cur != null && cur.Next != null)
            cur = cur.Next;
        return cur;
    }
    // Partitions the list taking the 
  // last element as the pivot
    static Node Partition(Node head, Node end, ref Node newHead, ref Node newEnd)
    {
        Node pivot = end;
        Node prev = null, cur = head, tail = pivot;
        // During partition, both the head and end of the list
        while (cur != pivot)
        {
            if (cur.Data < pivot.Data)
            {
                // First node that has a value less than the 
              // pivot - becomes the new head
                if (newHead == null)
                    newHead = cur;
                prev = cur;
                cur = cur.Next;
            }
            else
            {
                // Move cur node to the next of tail and change tail
                if (prev != null)
                    prev.Next = cur.Next;
                Node tmp = cur.Next;
                cur.Next = null;
                tail.Next = cur;
                tail = cur;
                cur = tmp;
            }
        }
        // If the pivot data is the smallest element in the current list
      // pivot becomes the head
        if (newHead == null)
            newHead = pivot;
        // Update newEnd to the current last node
        newEnd = tail;
        // Return the pivot node
        return pivot;
    }
    // Here the sorting happens exclusive of the end node
    static Node QuickSortRecur(Node head, Node end)
    {
        // Base condition
        if (head == null || head == end)
            return head;
        Node newHead = null, newEnd = null;
        // Partition the list newHead and newEnd will be updated by 
      // the partition function
        Node pivot = Partition(head, end, ref newHead, ref newEnd);
        // If pivot is the smallest element - no need to recurse for the left part
        if (newHead != pivot)
        {
            // Set the node before the pivot node as null
            Node tmp = newHead;
            while (tmp.Next != pivot)
                tmp = tmp.Next;
            tmp.Next = null;
            // Recurse for the list before pivot
            newHead = QuickSortRecur(newHead, tmp);
            // Change the Next of the last node of 
          // the left half to pivot
            tmp = GetTail(newHead);
            tmp.Next = pivot;
        }
        // Recurse for the list after the pivot element
        pivot.Next = QuickSortRecur(pivot.Next, newEnd);
        return newHead;
    }
    // The main function for quick sort. This is a wrapper over 
  // the recursive function QuickSortRecur
    static Node QuickSort(Node head)
    {
        return QuickSortRecur(head, GetTail(head));
    }
    // Driver's code
    static void Main()
    {
        Node a = null;
        a = Push(a, 5);
        a = Push(a, 20);
        a = Push(a, 4);
        a = Push(a, 3);
        a = Push(a, 30);
        Console.WriteLine("Linked List before sorting:");
        PrintList(a);
        // Function call
        a = QuickSort(a);
        Console.WriteLine("Linked List after sorting:");
        PrintList(a);
    }
}

Javascript

/* a node of the singly linked list */
class Node {
    constructor(val) {
        this.data = val;
        this.next = null;
    }
}

// The main function for quick sort. This is a wrapper over
// recursive function quickSortRecur()
class QuickSortLinkedList {
    constructor() {
        this.head = null;
    }

    addNode(data) {
        if (this.head == null) {
            this.head = new Node(data);
            return;
        }
        let curr = this.head;
        while (curr.next != null) {
            curr = curr.next;
        }
        let newNode = new Node(data);
        curr.next = newNode;
    }
/* A utility function to print linked list */
    printList(n) {
        while (n != null) {
            console.log(n.data);
            n = n.next;
        }
    }

// Partitions the list taking the last element as the pivot
    partitionLast(start, end) {
        if (start == end || start == null || end == null) {
            return start;
        }
        let pivot_prev = start;
        let curr = start;
        let pivot = end.data;
        while (start != end) {
            if (start.data < pivot) {
                pivot_prev = curr;
                let temp = curr.data;
                curr.data = start.data;
                start.data = temp;
                curr = curr.next;
            }
            start = start.next;
        }
        let temp = curr.data;
        curr.data = pivot;
        end.data = temp;
        return pivot_prev;
    }
// Function to sort 
    sort(start, end) {
        if (start == null || start == end || start == end.next) {
            return;
        }
        let pivot_prev = this.partitionLast(start, end);
        this.sort(start, pivot_prev);
        if (pivot_prev != null && pivot_prev == start) {
            this.sort(pivot_prev.next, end);
        } else if (pivot_prev != null && pivot_prev.next != null) {
            this.sort(pivot_prev.next.next, end);
        }
    }
}


// Driver code
let ll = new QuickSortLinkedList();
ll.addNode(30);
ll.addNode(3);
ll.addNode(4);
ll.addNode(20);
ll.addNode(5);
let N = ll.head;
while (N.next != null) {
    N = N.next;
}
console.log('\nLinked List before sorting');
ll.printList(ll.head)
ll.sort(ll.head, N);
console.log("\nLinked List after sorting");
ll.printList(ll.head);

Output

Linked List before sorting 
30 3 4 20 5 
Linked List after sorting 
3 4 5 20 30

Time complexity: O(n ^ 2)
Auxiliary Space: O(1)

Method 4: Sort Linked List using Merge Sort

Let the head be the first node of the linked list to be sorted and headRef be the pointer to head. Note that we need a reference to head in MergeSort() as the below implementation changes next links to sort the linked lists (not data at the nodes), so the head node has to be changed if the data at the original head is not the smallest value in the linked list.

MergeSort(headRef)
- If the head is NULL or there is only one element in the Linked List, then return.
- Else divide the linked list into two halves.
  - FrontBackSplit(head, &a, &b); /* a and b are two halves */
- Sort the two halves a and b.
  - MergeSort(a);
  - MergeSort(b);
- Merge the sorted a and b (using SortedMerge() discussed here) and update the head pointer using headRef.
  - *headRef = SortedMerge(a, b);

Below is the implementation of the above approach:

C++

// C++ code for linked list merged sort
#include <bits/stdc++.h>
using namespace std;

/* Link list node */
class Node {
public:
    int data;
    Node* next;
};

/* function prototypes */
Node* SortedMerge(Node* a, Node* b);
void FrontBackSplit(Node* source, Node** frontRef,
                    Node** backRef);

/* sorts the linked list by changing next pointers (not
 * data) */
void MergeSort(Node** headRef)
{
    Node* head = *headRef;
    Node* a;
    Node* b;

    /* Base case -- length 0 or 1 */
    if ((head == NULL) || (head->next == NULL)) {
        return;
    }

    /* Split head into 'a' and 'b' sublists */
    FrontBackSplit(head, &a, &b);

    /* Recursively sort the sublists */
    MergeSort(&a);
    MergeSort(&b);

    /* answer = merge the two sorted lists together */
    *headRef = SortedMerge(a, b);
}

/* See https:// www.geeksforgeeks.org/?p=3622 for details of
this function */
Node* SortedMerge(Node* a, Node* b)
{
    Node* result = NULL;

    /* Base cases */
    if (a == NULL)
        return (b);
    else if (b == NULL)
        return (a);

    /* Pick either a or b, and recur */
    if (a->data <= b->data) {
        result = a;
        result->next = SortedMerge(a->next, b);
    }
    else {
        result = b;
        result->next = SortedMerge(a, b->next);
    }
    return (result);
}

/* UTILITY FUNCTIONS */
/* Split the nodes of the given list into front and back
   halves, and return the two lists using the reference
   parameters. If the length is odd, the extra node should
   go in the front list. Uses the fast/slow pointer
   strategy. */
void FrontBackSplit(Node* source, Node** frontRef,
                    Node** backRef)
{
    Node* fast;
    Node* slow;
    slow = source;
    fast = source->next;

    /* Advance 'fast' two nodes, and advance 'slow' one node
     */
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }

    /* 'slow' is before the midpoint in the list, so split
    it in two at that point. */
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
}

/* Function to print nodes in a given linked list */
void printList(Node* node)
{
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
}

/* Function to insert a node at the beginning of the linked
 * list */
void 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 program to test above functions*/
int main()
{
    /* Start with the empty list */
    Node* res = NULL;
    Node* a = NULL;

    /* Let us create a unsorted linked lists to test the
functions Created lists shall be a: 2->3->20->5->10->15 */
    push(&a, 15);
    push(&a, 10);
    push(&a, 5);
    push(&a, 20);
    push(&a, 3);
    push(&a, 2);

    /* Sort the above created Linked List */
    MergeSort(&a);

    cout << "Sorted Linked List is: \n";
    printList(a);

    return 0;
}

// C code for linked list merged sort
#include <stdio.h>
#include <stdlib.h>

/* Link list node */
struct Node {
    int data;
    struct Node* next;
};

/* function prototypes */
struct Node* SortedMerge(struct Node* a, struct Node* b);
void FrontBackSplit(struct Node* source,
                    struct Node** frontRef,
                    struct Node** backRef);

/* sorts the linked list by changing next pointers (not
 * data) */
void MergeSort(struct Node** headRef)
{
    struct Node* head = *headRef;
    struct Node* a;
    struct Node* b;

    /* Base case -- length 0 or 1 */
    if ((head == NULL) || (head->next == NULL)) {
        return;
    }

    /* Split head into 'a' and 'b' sublists */
    FrontBackSplit(head, &a, &b);

    /* Recursively sort the sublists */
    MergeSort(&a);
    MergeSort(&b);

    /* answer = merge the two sorted lists together */
    *headRef = SortedMerge(a, b);
}

/* See https:// www.geeksforgeeks.org/?p=3622 for details of
this function */
struct Node* SortedMerge(struct Node* a, struct Node* b)
{
    struct Node* result = NULL;

    /* Base cases */
    if (a == NULL)
        return (b);
    else if (b == NULL)
        return (a);

    /* Pick either a or b, and recur */
    if (a->data <= b->data) {
        result = a;
        result->next = SortedMerge(a->next, b);
    }
    else {
        result = b;
        result->next = SortedMerge(a, b->next);
    }
    return (result);
}

/* UTILITY FUNCTIONS */
/* Split the nodes of the given list into front and back
   halves, and return the two lists using the reference
   parameters. If the length is odd, the extra node should
   go in the front list. Uses the fast/slow pointer
   strategy. */
void FrontBackSplit(struct Node* source,
                    struct Node** frontRef,
                    struct Node** backRef)
{
    struct Node* fast;
    struct Node* slow;
    slow = source;
    fast = source->next;

    /* Advance 'fast' two nodes, and advance 'slow' one node
     */
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }

    /* 'slow' is before the midpoint in the list, so split
    it in two at that point. */
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
}

/* Function to print nodes in a given linked list */
void printList(struct Node* node)
{
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}

/* Function to insert a node at the beginning of the linked
 * list */
void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct 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 program to test above functions*/
int main()
{
    /* Start with the empty list */
    struct Node* res = NULL;
    struct Node* a = NULL;

    /* Let us create a unsorted linked lists to test the
functions Created lists shall be a: 2->3->20->5->10->15 */
    push(&a, 15);
    push(&a, 10);
    push(&a, 5);
    push(&a, 20);
    push(&a, 3);
    push(&a, 2);

    /* Sort the above created Linked List */
    MergeSort(&a);

    printf("Sorted Linked List is: \n");
    printList(a);

    getchar();
    return 0;
}

Java

public class MergeSortLinkedList {
    // Link list node
    static class Node {
        int data;
        Node next;

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

    // Merge two sorted linked lists
    static Node sortedMerge(Node a, Node b) {
        Node result = null;

        // Base cases
        if (a == null)
            return b;
        if (b == null)
            return a;

        // Pick either a or b, and recur
        if (a.data <= b.data) {
            result = a;
            result.next = sortedMerge(a.next, b);
        } else {
            result = b;
            result.next = sortedMerge(a, b.next);
        }
        return result;
    }

    // Split the nodes of the given list into front and back halves
    // and return the two lists using the reference parameters
    // If the length is odd, the extra node should go in the front list
    static void frontBackSplit(Node source, Node[] frontRef, Node[] backRef) {
        Node slow = source;
        Node fast = source.next;

        // Advance 'fast' two nodes, and advance 'slow' one node
        while (fast != null) {
            fast = fast.next;
            if (fast != null) {
                slow = slow.next;
                fast = fast.next;
            }
        }

        // 'slow' is before the midpoint in the list, so split it in two at that point
        frontRef[0] = source;
        backRef[0] = slow.next;
        slow.next = null;
    }

    // Merge sort the linked list
    static void mergeSort(Node headRef) {
        Node head = headRef;
        Node a, b;

        // Base case -- length 0 or 1
        if (head == null || head.next == null) {
            return;
        }

        // Split head into 'a' and 'b' sublists
        Node[] frontRef = new Node[1];
        Node[] backRef = new Node[1];
        frontBackSplit(head, frontRef, backRef);
        a = frontRef[0];
        b = backRef[0];

        // Recursively sort the sublists
        mergeSort(a);
        mergeSort(b);

        // Answer = merge the two sorted lists together
        headRef = sortedMerge(a, b);
    }

    // Function to print nodes in a given linked list
    static void printList(Node node) {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
        System.out.println();
    }

    // Function to insert a node at the beginning of the linked list
    static Node push(Node headRef, int new_data) {
        // Allocate node
        Node new_node = new Node(new_data);

        // Link the old list off the new node
        new_node.next = headRef;

        // Move the head to point to the new node
        headRef = new_node;

        return headRef;
    }

    // Driver program to test above functions
    public static void main(String[] args) {
        // Start with the empty list
        Node res = null;
        Node a = null;

        // Let us create an unsorted linked list to test the functions
        // Created list shall be a: 2->3->20->5->10->15
        a = push(a, 15);
        a = push(a, 10);
        a = push(a, 5);
        a = push(a, 20);
        a = push(a, 3);
        a = push(a, 2);

        // Sort the above-created Linked List
        mergeSort(a);

        System.out.println("Sorted Linked List is: ");
        printList(a);
    }
}

Python

# Python3 program to merge sort of linked list

# create Node using class Node.


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


class LinkedList:
    def __init__(self):
        self.head = None

    # push new value to linked list
    # using append method
    def append(self, new_value):

        # Allocate new node
        new_node = Node(new_value)

        # if head is None, initialize it to new node
        if self.head is None:
            self.head = new_node
            return
        curr_node = self.head
        while curr_node.next is not None:
            curr_node = curr_node.next

        # Append the new node at the end
        # of the linked list
        curr_node.next = new_node

    def sortedMerge(self, a, b):
        result = None

        # Base cases
        if a == None:
            return b
        if b == None:
            return a

        # pick either a or b and recur..
        if a.data <= b.data:
            result = a
            result.next = self.sortedMerge(a.next, b)
        else:
            result = b
            result.next = self.sortedMerge(a, b.next)
        return result

    def mergeSort(self, h):

        # Base case if head is None
        if h == None or h.next == None:
            return h

        # get the middle of the list
        middle = self.getMiddle(h)
        nexttomiddle = middle.next

        # set the next of middle node to None
        middle.next = None

        # Apply mergeSort on left list
        left = self.mergeSort(h)

        # Apply mergeSort on right list
        right = self.mergeSort(nexttomiddle)

        # Merge the left and right lists
        sortedlist = self.sortedMerge(left, right)
        return sortedlist

    # Utility function to get the middle
    # of the linked list
    def getMiddle(self, head):
        if (head == None):
            return head

        slow = head
        fast = head

        while (fast.next != None and
                fast.next.next != None):
            slow = slow.next
            fast = fast.next.next

        return slow

# Utility function to print the linked list


def printList(head):
    if head is None:
        print(' ')
        return
    curr_node = head
    while curr_node:
        print(curr_node.data, end=" ")
        curr_node = curr_node.next
    print(' ')


# Driver Code
if __name__ == '__main__':
    li = LinkedList()

    # Let us create a unsorted linked list
    # to test the functions created.
    # The list shall be a: 2->3->20->5->10->15
    li.append(15)
    li.append(10)
    li.append(5)
    li.append(20)
    li.append(3)
    li.append(2)

    # Apply merge Sort
    li.head = li.mergeSort(li.head)
    print("Sorted Linked List is:")
    printList(li.head)

using System;

// Linked list node
class Node
{
    public int data;
    public Node next;
}

class LinkedListMergeSort
{
    // Function prototypes
    static Node SortedMerge(Node a, Node b)
    {
        Node result = null;

        // Base cases
        if (a == null)
            return b;
        else if (b == null)
            return a;

        // Pick either a or b, and recur
        if (a.data <= b.data)
        {
            result = a;
            result.next = SortedMerge(a.next, b);
        }
        else
        {
            result = b;
            result.next = SortedMerge(a, b.next);
        }
        return result;
    }

    // Split the nodes of the given list into front and back halves
    // and return the two lists using the reference parameters
    // If the length is odd, the extra node should go in the front list.
    // Uses the fast/slow pointer strategy.
    static void FrontBackSplit(Node source, out Node frontRef, out Node backRef)
    {
        Node fast;
        Node slow;
        slow = source;
        fast = source.next;

        // Advance 'fast' two nodes, and advance 'slow' one node
        while (fast != null)
        {
            fast = fast.next;
            if (fast != null)
            {
                slow = slow.next;
                fast = fast.next;
            }
        }

        // 'slow' is before the midpoint in the list, so split it in two at that point
        frontRef = source;
        backRef = slow.next;
        slow.next = null;
    }

    // Merge sort for linked list by changing next pointers
    // (not data)
    static void MergeSort(ref Node headRef)
    {
        Node head = headRef;
        Node a;
        Node b;

        // Base case -- length 0 or 1
        if (head == null || head.next == null)
            return;

        // Split head into 'a' and 'b' sublists
        FrontBackSplit(head, out a, out b);

        // Recursively sort the sublists
        MergeSort(ref a);
        MergeSort(ref b);

        // Answer = merge the two sorted lists together
        headRef = SortedMerge(a, b);
    }

    // Function to print nodes in a given linked list
    static void PrintList(Node node)
    {
        while (node != null)
        {
            Console.Write(node.data + " ");
            node = node.next;
        }
    }

    // Function to insert a node at the beginning of the linked list
    static void Push(ref Node headRef, int newData)
    {
        // Allocate node
        Node newNode = new Node();

        // Put in the data
        newNode.data = newData;

        // Link the old list to the new node
        newNode.next = headRef;

        // Move the head to point to the new node
        headRef = newNode;
    }

    // Driver program to test above functions
    static void Main()
    {
        // Start with the empty list
        Node a = null;

        // Create an unsorted linked list to test the functions
        // Created list shall be: 2->3->20->5->10->15
        Push(ref a, 15);
        Push(ref a, 10);
        Push(ref a, 5);
        Push(ref a, 20);
        Push(ref a, 3);
        Push(ref a, 2);

        // Sort the above created Linked List
        MergeSort(ref a);

        Console.Write("Sorted Linked List is: \n");
        PrintList(a);
    }
}

Javascript

/* Node class for linked list */
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

/* Function to merge two sorted linked lists */
function sortedMerge(a, b) {
  let result = null;
  /* Base cases */
  if (a == null) {
    return b;
  } else if (b == null) {
    return a;
  }
  /* Pick either a or b, and recur */
  if (a.data <= b.data) {
    result = a;
    result.next = sortedMerge(a.next, b);
  } else {
    result = b;
    result.next = sortedMerge(a, b.next);
  }
  return result;
}

/* Function to split the linked list into two halves */
function frontBackSplit(source) {
  let fast = source.next;
  let slow = source;

  /* Advance 'fast' two nodes, and advance 'slow' one node */
  while (fast != null) {
    fast = fast.next;
    if (fast != null) {
      slow = slow.next;
      fast = fast.next;
    }
  }

  /* 'slow' is before the midpoint in the list, so split it in two at that point. */
  const frontRef = source;
  const backRef = slow.next;
  slow.next = null;

  return { frontRef, backRef };
}

/* Function to perform merge sort on linked list */
function mergeSort(headRef) {
  let head = headRef;
  let a, b;

  /* Base case -- length 0 or 1 */
  if (head == null || head.next == null) {
    return head;
  }

  /* Split head into 'a' and 'b' sublists */
  const { frontRef, backRef } = frontBackSplit(head);

  /* Recursively sort the sublists */
  a = mergeSort(frontRef);
  b = mergeSort(backRef);

  /* Merge the two sorted lists */
  return sortedMerge(a, b);
}

/* Function to print the linked list */
function printList(node) {
  while (node != null) {
    process.stdout.write(node.data + " ");
    node = node.next;
  }
  console.log();
}

/* Driver program to test above functions */
function main() {
  /* Start with the empty list */
  let res = null;
  let a = null;

  /* Let us create an unsorted linked list to test the functions */
  a = new Node(15);
  a.next = new Node(10);
  a.next.next = new Node(5);
  a.next.next.next = new Node(20);
  a.next.next.next.next = new Node(3);
  a.next.next.next.next.next = new Node(2);

  /* Sort the above created linked list */
  a = mergeSort(a);

  console.log("Sorted Linked List is:");
  printList(a);
}

/* Invoke the main function */
main();

Output

Sorted Linked List is: 
2 3 5 10 15 20

Time complexity: O(n log n)
Auxiliary Space: O(1)

RishabhPrabhu

Improve

Singly Linked List Tutorial

Sorting a Singly Linked List

Method 1: Sort Linked List using Bubble Sort

Method 2: Sort Linked List using Insertion Sort

Method 3: Sort Linked List using Quick Sort

Method 4: Sort Linked List using Merge Sort

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?