https://leetcode.com/problems/insertion-sort-list/

Thought

The idea is simple: we gradly build the sorted list the head of which is a dummyHead. However, extra caution is needed when we traverse the original list, we need to make a copy of next of head.next before we insert the head into the new list since insertion will change where the head.next point to.

How to insert a node?

Given the head of a sorted LinkedList, how to insert the node into proper place?

The proper slot is the one that head.val < node.val and head.next.val > node.val if head.next != null, then make

1
2
3
tmp = head.next; 
head.next = node; 
node.next = tmp;

If head.next == null, then we just append to the head: head.next = node, however, if we add tmp = head.next, it would hurt, tmp simply == null.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dumHead = new ListNode(Integer.MIN_VALUE);
        while (head != null) {
            ListNode next = head.next;
            insert(head, dumHead);
            head = next;
        }
        return dumHead.next;
    }
    private void insert(ListNode node, ListNode head) {
        while (head.val < node.val && head.next != null && head.next.val < node.val) {
            head = head.next;
        }
        ListNode pre = head.next;
        head.next = node;
        node.next = pre;
    }
}