{x}
blog image

Insertion Sort List

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:

  1. Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
  2. 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.
  3. 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

Solution Explanation:

This problem requires sorting a singly linked list using the insertion sort algorithm. The solution uses a dummy node to simplify the insertion process.

Algorithm:

  1. Handle Base Cases: If the list is empty or has only one node, it's already sorted, so return the head.

  2. Initialize: Create a dummy node with the value of the head node. This dummy node will always point to the beginning of the sorted portion of the list. pre will track the last node in the sorted portion, and cur will iterate through the unsorted portion.

  3. Iteration: The while cur loop iterates through the unsorted portion of the list.

  4. Sorted Condition: If the current node's value (cur.val) is greater than or equal to the previous node's value (pre.val), it's already in its correct sorted position. We move pre and cur to the next nodes and continue.

  5. Insertion: If cur.val is less than pre.val, it needs to be inserted into the sorted portion. A second inner loop (while p.next.val <= cur.val) finds the correct position (p) to insert cur.

  6. Rewiring: The next few lines perform the actual insertion by rewiring pointers:

    • t = cur.next: Stores the next node of cur temporarily.
    • cur.next = p.next: Connects cur to the node after p.
    • p.next = cur: Inserts cur after p.
    • pre.next = t: Connects the node before cur to the node after cur.

  7. Update: cur is updated to t to continue processing the remaining unsorted portion.

  8. Return: Finally, return the next of the dummy node, which points to the head of the sorted list.

Time Complexity: O(n^2), where n is the number of nodes. This is because of the nested loops; the outer loop iterates n times, and the inner loop, in the worst case, iterates up to the current index. This is characteristic of insertion sort.

Space Complexity: O(1). The algorithm uses only a constant amount of extra space for pointers.

Code Explanations (Python3 Example):

The Python code closely follows the algorithm described above. Note the use of a ListNode class (which you would need to define separately based on the problem's definition of a linked list node):

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        # ... (rest of the code as shown before) ...

The other language examples (Java and JavaScript) follow a very similar structure and logic, adapting the syntax to their respective languages. The core algorithm remains the same.