#147

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Insertion Sort List

Sort a singly linked list using insertion sort by carefully manipulating pointers to maintain a sorted order efficiently.

linked list sorting

Problem Statement

You are given the head of a singly linked list. Sort the list using insertion sort, returning the head of the newly ordered list. Each node must be repositioned by adjusting pointers without creating extra lists.

The insertion sort process involves maintaining a sorted portion of the list and repeatedly taking the next unsorted node to insert into its proper location. For example, starting with head = [4,2,1,3], the sorted section begins with 4, and each remaining node is inserted in order until the entire list is sorted.

Examples

Example 1

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

Output: [1,2,3,4]

Example details omitted.

Example 2

Input: head = [-1,5,3,4,0]

Output: [-1,0,3,4,5]

Example details omitted.

Constraints

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

Solution Approach

Iterative Node Insertion

Initialize a dummy node pointing to the sorted portion. Iterate through the original list and for each node, find the insertion point in the sorted list by comparing values. Adjust pointers to insert the node without losing connections.

Handling Head and Consecutive Nodes

Special care is needed when inserting at the beginning of the list or when multiple consecutive nodes are smaller than the current sorted node. Update the dummy or head pointer appropriately to avoid losing nodes and ensure correct ordering.

In-Place Sorting Without Extra Space

Use only constant extra space by re-linking nodes rather than creating new nodes or arrays. Traverse the list once for each insertion to maintain O(N^2) time and O(1) space complexity, preserving the linked-list structure.

Complexity Analysis

Metric	Value
Time	\mathcal{O}(N^2)
Space	\mathcal{O}(1)

Time complexity is O(N^2) because each node may require scanning the sorted portion to find its position. Space complexity is O(1) since all operations are done by reassigning existing pointers without allocating additional storage.

What Interviewers Usually Probe

Asks about pointer manipulation and edge cases when inserting at head.
Checks if you can maintain O(1) space while performing insertions.
May present a partially sorted list to observe iterative insertion handling.

Common Pitfalls or Variants

Common pitfalls

Forgetting to update the next pointer before insertion, leading to lost nodes.
Incorrect handling when inserting a node before the head of the sorted list.
Confusing consecutive nodes, which can result in incorrect ordering or infinite loops.

Follow-up variants

Sorting a doubly linked list using insertion sort with similar pointer updates.
Implementing insertion sort recursively on a linked list.
Optimizing by reducing redundant traversal when inserting consecutive nodes already in order.

FAQ

What is the main strategy for solving Insertion Sort List?

The strategy is to iterate through the list, and for each node, find the correct spot in the sorted portion by adjusting pointers carefully.

Can I use extra arrays for Insertion Sort List?

No, the problem expects in-place pointer manipulation with O(1) additional space, so no extra arrays should be used.

How do I handle inserting a node before the head?

Use a dummy node or update the head pointer directly to insert nodes smaller than the current head safely.

What is the time complexity for this linked-list insertion sort?

The worst-case time complexity is O(N^2) since each node may require scanning the sorted portion of the list.

What linked-list pattern does this problem focus on?

It emphasizes linked-list pointer manipulation, specifically maintaining correct links while performing insertion sort.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        dummy = ListNode(head.val, head)
        pre, cur = dummy, head
        while cur:
            if pre.val <= cur.val:
                pre, cur = cur, cur.next
                continue
            p = dummy
            while p.next.val <= cur.val:
                p = p.next
            t = cur.next
            cur.next = p.next
            p.next = cur
            pre.next = t
            cur = t
        return dummy.next

Continue Practicing

#148 sort list #146 lru cache #143 reorder list