algoadvance

Leetcode 147. Insertion Sort List

Problem Statement

You are given the head of a singly linked list. You need to sort the list using insertion sort and return the sorted list’s head.

Definition for singly-linked list:

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Clarifying Questions

1. What should we return if the input list is empty or contains a single node?
   • If the input list is empty or contains a single node, return the list as it is.
2. Are there any constraints on the values of the nodes?
   • The problem statement does not specify any constraints, so assume node values can be any integer.
3. Should the sorting be stable or unstable?
   • Insertion sort is naturally stable, so the relative order of equal elements should be maintained.
4. Will the list contain any loops or will it always be a proper singly linked list?
   • Assume the list is a proper singly linked list with no loops.

Strategy

Insertion Sort works similarly to the way you sort playing cards in your hands. We take one element at a time and place it in the correct position relative to the already sorted elements.

Approach:

1. Initialize a dummy node which helps to handle edge cases easily.
2. Iterate over the original list node by node.
3. For each node, find its correct position in the sorted part of the list.
4. Insert it into the correct position.
5. Continue until all nodes are sorted.

We’ll use a dummy node at the start of our sorted list to simplify insertion logic by avoiding special cases for head insertions.

Code

Here is the Java implementation of the problem:

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return null;
        }
        
        ListNode dummy = new ListNode(0); // dummy node
        ListNode curr = head; // pointer to iterate through the original list
        
        while (curr != null) {
            ListNode prev = dummy; // always point to the dummy node initially
            ListNode next = curr.next; // store next node to move forward later
            
            // Find the correct position to insert the current node
            while (prev.next != null && prev.next.val < curr.val) {
                prev = prev.next;
            }
            
            // Insert the current node in the sorted list
            curr.next = prev.next;
            prev.next = curr;
            
            // Move to the next node in the original list
            curr = next;
        }
        
        return dummy.next; // the sorted list starts from dummy.next
    }
}

Time Complexity

• Time Complexity: O(n^2)
  • In the worst case, for each node in the list, we may need to traverse the entire sorted part to find the correct position. Thus, the time complexity is quadratic, O(n^2).
• Space Complexity: O(1)
  • The space usage is constant because we only use a few additional pointers and no extra space that scales with input size. The sorting is done in place on the linked list.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?