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:
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:
[1, 5000]
.-5000 <= Node.val <= 5000
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:
Handle Base Cases: If the list is empty or has only one node, it's already sorted, so return the head.
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.
Iteration: The while cur
loop iterates through the unsorted portion of the list.
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.
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
.
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
.Update: cur
is updated to t
to continue processing the remaining unsorted portion.
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.