We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Insertion Sort List

Difficulty: Medium

Problem Description

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.

Key Insights

  • Insertion sort builds a sorted output list one element at a time by repeatedly removing elements from the input list and inserting them in the correct position.
  • The algorithm maintains a reference to the sorted part of the list while iterating through the unsorted part.
  • It is important to handle the linked list nodes effectively, as we cannot directly access elements by index.

Space and Time Complexity

Time Complexity: O(n^2) - In the worst case, each insertion takes linear time, leading to a quadratic time complexity overall. Space Complexity: O(1) - We sort the list in place, using only a constant amount of extra space.

Solution

The solution involves iterating through the linked list and inserting each node into its proper position in a new sorted list. We utilize a dummy node to simplify the insertion process. The approach involves:

  1. Creating a new sorted list initialized with a dummy head.
  2. Iterating through each node of the original list.
  3. For each node, finding the appropriate position in the sorted list and inserting it there.

Code Solutions

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def insertionSortList(head):
    dummy = ListNode(0)  # Create a dummy node for the sorted list
    current = head  # Pointer to iterate through the original list
    
    while current:
        # At each iteration, we need to insert the current node into the sorted part
        prev = dummy  # Start from the dummy node
        # Find the correct position to insert the current node
        while prev.next and prev.next.val < current.val:
            prev = prev.next
        
        # Insert the current node in the sorted list
        next_temp = current.next  # Store the next node to process
        current.next = prev.next  # Point current node to the next of prev
        prev.next = current  # Link prev to the current node
        current = next_temp  # Move to the next node in the original list
    
    return dummy.next  # Return the sorted list starting from the node after dummy
← Back to All Questions