Introduction

In this blog post, we will explore how to solve the LeetCode problem "147" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head. The steps of the insertion sort algorithm: Insertion sort iterates, consuming one input element each repetition and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there. It repeats until no input elements remain. The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration. Example 1: Input: head = [4,2,1,3] Output: [1,2,3,4] Example 2: Input: head = [-1,5,3,4,0] Output: [-1,0,3,4,5] Constraints: The number of nodes in the list is in the range [1, 5000]. -5000 <= Node.val <= 5000

Explanation

• Iterate through the unsorted portion: Maintain a sorted sublist at the beginning of the linked list. For each element in the unsorted portion, find its correct position within the sorted sublist.
  • Insert into the sorted portion: Insert the current element into its correct position in the sorted sublist by adjusting the next pointers of the nodes.
  • Handle edge cases carefully: Pay attention to inserting at the head of the list or at the end.

• Time Complexity: O(n^2), where n is the number of nodes in the linked list. Space Complexity: O(1).

Code

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

def insertionSortList(head: ListNode) -> ListNode:
    """
    Sorts a singly linked list using insertion sort.

    Args:
        head: The head of the linked list.

    Returns:
        The head of the sorted linked list.
    """

    if not head or not head.next:
        return head

    dummy_head = ListNode(0)  # Dummy head to simplify insertion at the beginning
    dummy_head.next = head
    sorted_tail = head
    curr = head.next

    while curr:
        if curr.val >= sorted_tail.val:
            sorted_tail = curr
            curr = curr.next
        else:
            # Remove curr from its current position
            sorted_tail.next = curr.next

            # Find the correct position for curr in the sorted portion
            prev = dummy_head
            while prev.next and prev.next.val < curr.val:
                prev = prev.next

            # Insert curr into the sorted portion
            curr.next = prev.next
            prev.next = curr

            curr = sorted_tail.next

    return dummy_head.next