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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Insertion Sort List

Number: 147

Difficulty: Medium

Paid? No

Companies: Google, Microsoft

Problem Description

Given the head of a singly linked list, sort the list using insertion sort and return the head of the sorted list. Insertion sort iterates through the list and, at each iteration, takes one node and inserts it into the proper position in the already sorted portion of the list.

Key Insights

  • Use a dummy node to simplify insertions, especially at the beginning of the list.
  • Iterate through each node of the original list.
  • For current node, find the correct insertion point in the sorted portion.
  • Insert the node by adjusting pointers, ensuring no additional memory is used apart from pointers.
  • The algorithm is similar to the usual array insertion sort, but works with linked list nodes.

Space and Time Complexity

Time Complexity: O(n²) in the worst case, where n is the number of nodes in the list. Space Complexity: O(1) since only a few extra pointers are used.

Solution

The solution involves creating a dummy node that acts as the start of the sorted sublist. Iterate through each node in the original list; for each node, traverse the sorted sublist from the dummy node to locate the correct insertion point. After finding the location, adjust the pointers so that the node is inserted in its proper order. This in-place method ensures that the sort uses constant space. Special attention is required when handling edge cases such as inserting at the beginning of the sorted list.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val  # Initialize the node's value.
        self.next = next  # Initialize the reference to the next node.

def insertionSortList(head: ListNode) -> ListNode:
    # Create a dummy node to simplify edge cases.
    dummy = ListNode(0)
    current = head  # Current node to be inserted.
    
    while current:
        # Save the next node to process.
        next_temp = current.next
        # Start at the beginning of the sorted list.
        pre = dummy
        # Find the correct spot to insert current.
        while pre.next and pre.next.val < current.val:
            pre = pre.next
        # Insert current between pre and pre.next.
        current.next = pre.next
        pre.next = current
        # Move to the next node in the original list.
        current = next_temp
    return dummy.next  # Return the head of the sorted list.
← Back to All Questions