algoadvance

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

Example: Input: head = [4,2,1,3] Output: [1,2,3,4]

Constraints:

• The number of nodes in the list is in the range [1, 5000].
• -5000 <= Node.val <= 5000

Clarifying Questions:

1. Are the node values within a specific range?
   • Yes, -5000 <= Node.val <= 5000.
2. Is it guaranteed that the list has at least one node?
   • Yes, since the number of nodes is in the range [1, 5000].

Strategy:

1. Create a Sentinal Node: This helps simplify edge cases where the node is inserted at the head.
2. Traverse the List: For each node, find the right position in the sorted part of the list and insert the node there.
3. Sorted Insert Function: Create a helper function to insert a given node into the already sorted part of the list.
4. Maintain Pointers: We need several pointers:
   • current to traverse the list.
   • prev to point to the node before the insertion point in the sorted list.
   • next to temporarily store the next node in the original list during insertion.

Code:

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

def insertionSortList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    
    # Create a sentinel (dummy) node that will help in managing the sorted list
    sentinel = ListNode(0)
    sentinel.next = head
    current = head.next
    sentinel.next.next = None
    
    while current:
        # Keep the next node to process
        next_to_process = current.next
        
        # Insert the current node into the sorted part
        prev = sentinel
        next_sorted = sentinel.next
        while next_sorted and next_sorted.val < current.val:
            prev = next_sorted
            next_sorted = next_sorted.next
        
        # Current's insertion
        current.next = next_sorted
        prev.next = current
        
        # Move to the next node
        current = next_to_process
    
    return sentinel.next

Time Complexity:

• Time Complexity: O(n^2) in the worst case since every insertion might need a full traversal of the sorted part of the list.
• Space Complexity: O(1) because we are using a constant amount of extra space i.e., pointers and a sentinel node.

Try our interview co-pilot at AlgoAdvance.com

• 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?