CODEWITHSUNDEEP
sortingdata-structureslinked-listquicksort
Abhishek Jaiswal
Abhishek Jaiswal

Reputation: 308

How to implement quick sort for singly linked list?

I know that quick sort can't be applied on singly linked list directly.

Some modifications are needed in quick sort to make it compatible with a singly linked list.

But I am not getting how to do this.

Note:- I don't want to swap the value of one node with another node. Indeed I want to sort the linked list by changing the next pointer of required nodes.

So please elaborate, how this can be done.

Upvotes: 1

Views: 523

Answers (1)

trincot
trincot

Reputation: 350137

Here is how you could do it:

  • Identify the tail node of the (sub)list. Also call this the pivot node.
  • Traverse the list and move a node after the current tail node when its value is greater than the pivot's value. To be able to move nodes, you'll need to have a reference that follows behind the current node as you traverse the list. Make the moved node the tail node (the pivot node no longer is the tail node now). Stop this iteration when the pivot node is encountered.
  • Now you have two sublists. Recur into those to repeat the above logic.

Here is an implementation in JavaScript:

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

function quickSort(head, tail) {
    if (tail == null || head == null || head == tail) return head;
    let pivot = tail;
    let curr = head;
    let prev = null;
    while (curr != pivot) {
        let next = curr.next;
        if (curr.value > pivot.value) {
            // Move node after tail
            if (prev == null) {
                 head = next;
            } else {
                 prev.next = next;
            }
            curr.next = tail.next;
            tail.next = curr;
            tail = curr;
        } else {
            prev = curr;
        }
        curr = next;
    }
    // Sort right and left sublists with recursion
    if (pivot != tail) pivot.next = quickSort(pivot.next, tail);
    return quickSort(head, prev);
}

// Some helper/utility functions
function getTail(head) {
    if (head == null) return null;
    while (head.next != null) {
        head = head.next;
    }
    return head;
}

function createList(arr) {
    let head = null;
    for (let i = arr.length - 1; i >= 0; i--) {
        head = new Node(arr[i], head);
    }
    return head;
}

function toArray(head) {
    let arr = [];
    while (head != null) {
        arr.push(head.value);
        head = head.next;
    }
    return arr;
}

// Demo:
// Create list from array
let head = createList([4,2,6,1,5,3]);
// Apply quick sort
let tail = getTail(head);
head = quickSort(head, tail);
// Print
console.log(toArray(head));

Upvotes: 2

Related Questions