147. Insertion Sort List

Problem Description

In this problem, the goal is to sort a singly linked list using the insertion sort algorithm. A singly linked list is a collection of nodes where each node contains a value and a reference to the next node in the list. The insertion sort algorithm sorts a list or an array by taking one element at a time and inserting it into its correct position in a separate sorted part of the list.

The process for insertion sort in the context of a linked list involves the following steps:

Start with the second element of the list (since a list with one element is already sorted), and for each element—
Compare with the elements in the sorted part of the list (starting from the beginning) to find the correct position.
Insert the element at the found position in the sorted part.
Continue the process until we reach the end of the original list, and no elements are left to sort.

The challenge in this problem lies in properly manipulating the pointers in the linked list without losing track of the nodes.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The provided solution uses a dummy node to simplify edge cases and ensure that there's always a ‘previous’ node for comparison, thus streamlining the insertion process.

Here is the intuition behind the provided solution code:

If the list is empty or has only one element, there is no need to sort, so we return the head as is.
We create a dummy node and set its next pointer to the head of the list.
We use two pointers pre and cur, starting at the dummy and head positions, respectively, to traverse the list. The pre pointer checks if the cur pointer's value is in the right position (i.e., if it's greater than or equal to the current sorted part).
If the current node value is in the right place, simply move both pointers one step forward.
If the current node needs to be repositioned, we use another pointer p that starts at the dummy node and finds the correct position in the sorted part of the list where the current node (cur) should be inserted.
Insert the current node (cur) into the sorted part of the list at the correct position.
Reconnect the pre.next to cur.next to maintain the unsorted part of the list without the newly inserted node.
Repeat the process until cur reaches the end of the list.
Return dummy.next, which now points to the head of the newly sorted linked list.

The core idea of this solution is keeping track of where the node needs to be inserted in the already sorted part of the list and carefully managing node pointers to maintain linked list integrity throughout the sort.

Learn more about Linked List and Sorting patterns.

Solution Approach

The solution implements the insertion sort algorithm specifically tailored to a singly linked list. To understand this approach, we visualize the list as comprising two parts: the sorted part and the unsorted part. Initially, the sorted part contains just the first element, and the rest of the list is considered unsorted.

The code uses a dummy node, which is a common technique when dealing with linked list operations, to simplify handling edge cases like inserting at the beginning of the list.

Here's how the code works step-by-step:

A dummy node is created and points to the head of the list. This dummy node acts as the anchor for the start of the sorted list.
Two pointers, pre and cur, are used. pre starts at the dummy node and cur starts at the actual head of the list.
The while loop runs as long as cur is not None, which means that there are elements in the unsorted part.
Inside the loop, we initially check if the pre value is less than or equal to cur value. If it is, it means that the cur node is already in the right position relative to the pre node, and both pre and cur advance to the next nodes.
If the pre value is greater than the cur value, we need to find the correct spot to insert cur into the already-sorted part of the list.
The code then uses another pointer, p, which starts from the dummy and traverses the list to find the insert position. This loop continues until p.next.val is greater than cur.val, indicating the position where cur should be placed.
Next, cur is removed from its current position, and its next pointer is stored temporarily in t.
cur is then inserted into the sorted part by setting cur.next to p.next and then setting p.next to cur.
The old pre node is then connected to t, effectively removing the original cur and continuing with the rest of the list.
cur is updated to t, and the cycle continues until all elements are sorted.

This code neatly handles the insertion sort logic without needing an additional data structure other than the given linked list. The use of pointers to nodes (pre, cur, p, and t) is essential to perform the required operations without losing any part of the list.

This algorithm has a time complexity of O(n^2) in the worst case because, for each element, it potentially iterates through the entire sorted part to find the insert position. The space complexity is O(1) since the sort is performed in place without allocating any additional data structures.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach. Imagine we have a singly linked list with the following values:

4 -> 2 -> 1 -> 3

We want to sort this list in ascending order using the insertion sort algorithm described in our solution approach.

Initial Setup:

We create a dummy node.
The dummy node's next points to 4, the head of our unsorted list.
pre starts at the dummy node, and cur starts at the head (value 4).

Now, we iterate through the list to sort it:

Step 1:

List: dummy -> 4 -> 2 -> 1 -> 3
Since there's nothing preceding 4, it's already in the correct position (the sorted part has only one element).
Move cur to the next node (2). pre still points to the dummy.

Step 2:

List: dummy -> 4 -> 2 -> 1 -> 3
Compare cur (value 2) with pre.next (value 4).
Since 2 is less than 4, 2 must be moved to the correct position.
We introduce pointer p starting at dummy to look for the insertion point for 2.
Since dummy.next (value 4) is greater than 2, we insert 2 after dummy.
Update the connections: dummy.next becomes 2, 2.next becomes 4.
Now the sorted list is dummy -> 2 -> 4.

Step 3:

List: 2 -> 4 -> 1 -> 3 (with dummy pointing to 2)
Now, cur is pointing to 1. We compare it with the sorted part of the list.
Again p starts from dummy and moves to find where to insert 1.
Since 1 is less than 2, it should be inserted at the beginning.
Connect dummy.next to 1, and 1.next to 2.
The sorted list now is dummy -> 1 -> 2 -> 4.

Step 4:

List: 1 -> 2 -> 4 -> 3 (with dummy pointing to 1)
cur is now pointing to 3. As before, use p to find the position for 3.
We place 3 between 2 and 4, since 3 is greater than 2 and less than 4.
Update pointers: 2.next becomes 3, and 3.next becomes 4.
Sorted list is now dummy -> 1 -> 2 -> 3 -> 4.

After sorting:

Finally, we have dummy -> 1 -> 2 -> 3 -> 4.
Since dummy is our initial node, the head of the sorted list is dummy.next, which points to 1.

The final sorted linked list is:

1 -> 2 -> 3 -> 4

This walkthrough demonstrates how the insertion sort algorithm is applied to a singly linked list, efficiently repositioning nodes by manipulating pointers and ensuring the list stays connected throughout the sorting process.

Solution Implementation

1# Definition for singly-linked list.
2class ListNode:
3    def __init__(self, value=0, next_node=None):
4        self.value = value
5        self.next = next_node
6
7class Solution:
8    def insertionSortList(self, head: ListNode) -> ListNode:
9        # If the list is empty or has only one element, it's already sorted.
10        if head is None or head.next is None:
11            return head
12      
13        # Initialize a dummy node to help with insertion later.
14        dummy_node = ListNode(0)
15        dummy_node.next = head
16      
17        # 'previous' tracks the last node before the one being sorted, 'current' is the node being sorted.
18        previous, current = head, head.next
19      
20        # Iterate while there are nodes to sort.
21        while current:
22            if previous.value <= current.value:
23                # The current node is already in the correct place.
24                previous, current = current, current.next
25            else:
26                # Find the correct place to insert the current node.
27                insert_position = dummy_node
28                while insert_position.next.value <= current.value:
29                    insert_position = insert_position.next
30              
31                # Perform the insertion.
32                temp = current.next
33                current.next = insert_position.next
34                insert_position.next = current
35                previous.next = temp
36              
37                # Set 'current' to the next node to sort.
38                current = temp
39      
40        # The list is now sorted, return it starting from the node after dummy node.
41        return dummy_node.next
42

1class Solution {
2    public ListNode insertionSortList(ListNode head) {
3        // If the list is empty or has only one item, it's already sorted.
4        if (head == null || head.next == null) {
5            return head;
6        }
7      
8        // Initialize the dummy node with an initial value.
9        ListNode dummy = new ListNode(0);
10        // Previous and current pointers for traversal.
11        ListNode previous = dummy, current = head;
12      
13        // Iterate over the list to sort each element.
14        while (current != null) {
15            // If the value at previous is less than or equal to the current's value, move the pointers forward.
16            if (previous.val <= current.val) {
17                previous = current;
18                current = current.next;
19                continue;
20            }
21            // Find the correct position for the current node in the sorted part of the list
22            ListNode position = dummy;
23            while (position.next != null && position.next.val <= current.val) {
24                position = position.next;
25            }
26            // Insert current node in the correct position.
27            ListNode temp = current.next;
28            current.next = position.next;
29            position.next = current;
30          
31            // Move the previous pointer's next to temp and update current to temp.
32            previous.next = temp;
33            current = temp;
34        }
35        // Return the next node of dummy since the first node is a placeholder.
36        return dummy.next;
37    }
38}
39
40// Definition for singly-linked list.
41class ListNode {
42    int val;
43    ListNode next;
44    // Constructor to initialize a node with no next element.
45    ListNode() {}
46  
47    // Constructor to initialize a node with a value.
48    ListNode(int val) { this.val = val; }
49  
50    // Constructor to initialize a node with a value and a next element.
51    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
52}
53

1// Definition for singly-linked list.
2struct ListNode {
3    int val;
4    ListNode *next;
5
6    ListNode(int x) : val(x), next(nullptr) {}
7    ListNode(int x, ListNode *next) : val(x), next(next) {}
8};
9
10/**
11 * Sorts a linked list using the insertion sort algorithm.
12 * @param head - The head of the singly linked list to be sorted.
13 * @return The head of the linked list sorted in ascending order.
14 */
15ListNode* insertionSortList(ListNode* head) {
16    // If the list is empty or has only one node, no sorting is needed.
17    if (!head || !(head->next)) {
18        return head;
19    }
20
21    // The dummy node is used as a placeholder to help with inserting nodes at the beginning of the list.
22    ListNode dummy(0);
23    ListNode *previousNode = &dummy;
24    ListNode *currentNode = head;
25
26    while (currentNode) {
27        // If the current node is already in the correct position, just move forward.
28        if (previousNode->val <= currentNode->val) {
29            previousNode = currentNode;
30            currentNode = currentNode->next;
31            continue;
32        }
33
34        // Find the correct position to insert the current node by traversing from the start of the list.
35        ListNode *positionToInsert = &dummy;
36        while (positionToInsert->next && positionToInsert->next->val <= currentNode->val) {
37            positionToInsert = positionToInsert->next;
38        }
39
40        // Perform the insertion.
41        ListNode *nextNode = currentNode->next;
42        currentNode->next = positionToInsert->next;
43        positionToInsert->next = currentNode;
44
45        // Link the previous part to the new next position as needed.
46        // This does not change in the case when the previous node is equal to current node
47        // Such case can happen when the previous node is the dummy node and the current node
48        // is the first node being inserted in the sorted part.
49        // After insertion, the previous (dummy) node directly points to the new current node.
50        if(previousNode != currentNode)
51            previousNode->next = nextNode;
52
53        // Move the current node to the next position.
54        currentNode = nextNode;
55    }
56
57    // The dummy's next node is now the head of the sorted list.
58    return dummy.next;
59}
60
61// The above function can be utilized by creating `ListNode` objects and passing the head to `insertionSortList`.
62

1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5    val: number;
6    next: ListNode | null;
7
8    constructor(val: number = 0, next: ListNode | null = null) {
9        this.val = val;
10        this.next = next;
11    }
12}
13
14/**
15 * Sorts a linked list using insertion sort algorithm.
16 * @param {ListNode | null} head - The head of the singly linked list to be sorted.
17 * @return {ListNode | null} The head of the linked list sorted in ascending order.
18 */
19const insertionSortList = (head: ListNode | null): ListNode | null => {
20    // If the list is empty or has only one node, no sorting is needed.
21    if (head === null || head.next === null) {
22        return head;
23    }
24
25    // The dummy node is used as a placeholder to help with inserting nodes at the beginning of the list.
26    let dummy: ListNode = new ListNode(0);
27    let previousNode: ListNode = dummy;
28    let currentNode: ListNode | null = head;
29
30    while (currentNode !== null) {
31        // If the current node is already in the correct position, just move forward.
32        if (previousNode.val <= currentNode.val) {
33            previousNode = currentNode;
34            currentNode = currentNode.next;
35            continue;
36        }
37
38        // Find the correct position to insert the current node by traversing from the start.
39        let positionToInsert: ListNode = dummy;
40        while (positionToInsert.next !== null && positionToInsert.next.val <= currentNode.val) {
41            positionToInsert = positionToInsert.next;
42        }
43
44        // Perform the insertion.
45        let nextNode: ListNode | null = currentNode.next;
46        currentNode.next = positionToInsert.next;
47        positionToInsert.next = currentNode;
48
49        // Link the previous part to the next position.
50        previousNode.next = nextNode;
51      
52        // Move the current node to the next position.
53        currentNode = nextNode;
54    }
55
56    // The dummy's next node is now the head of the sorted list.
57    return dummy.next;
58};
59
60// The above function can be utilized by creating `ListNode` objects and passing the head to `insertionSortList`.
61

Time and Space Complexity

The time complexity of the insertion sort algorithm is generally O(n^2) for a linked list, where n is the number of elements in the linked list. This is because the algorithm consists of two nested loops: the outer loop runs once for every element, and the inner loop can run up to n times in the worst case (when the list is in reverse order). In the best case, when the list is already sorted, the time complexity is O(n). However, for the average and worst cases, since each element could potentially be compared with all the already sorted elements, the resultant complexity remains O(n^2).

The space complexity of the code is O(1) because it does not use additional space proportional to the input size. The sorting is done in place within the input list, and only a fixed number of extra pointers are used, irrespective of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know