147. [M] Insertion Sort List

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

难点在于细节。通常这种问题，都会设置一个 dummy 伪节点做为头结点。

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // (dummy) -> (4/head) -> (2) -> (1) -> (3)
        
        while (head != null && head.next != null) {
            if (head.val < head.next.val) {
                head = head.next;
                continue;
            }
            
            ListNode p = dummy;
            // (dummy/p) -> (4/head) -> (2) -> (1) -> (3)
            
            while (p.next.val < head.next.val) {
                p = p.next;
            }
            // (dummy/p) -> (4/head) -> (2) -> (1) -> (3)
            
            ListNode t = head.next;
            // (dummy/p) -> (4/head) -> (2/t) -> (1) -> (3)
            head.next = head.next.next;
            // (dummy/p) -> (4/head) -> (1) -> (3)
            // (2/t) -> (1) -> (3)
            t.next = p.next;
            // (dummy/p) -> (4/head) -> (1) -> (3)
            // (2/t) -> (4/head) -> (1) -> (3)
            p.next = t;
            // (dummy/p) -> (2/t) -> (4/head) -> (1) -> (3)
        }
        return dummy.next;
    }
}

理解

对于 (1/a) -> (2/b) -> (3) -> (4) 这种链条，要将 3 移动到 1 2 之间，顺序是

1. 用一个临时节点 c，保存 3 的下一个节点 4 的指针

2. b 指向 c 的下一个节点 4，此时 c 节点断开

3. c 指向 b

4. a 指向 c

为了便于理解，可以想象这是挂在某个位置的一个环环相扣的链条，中间一旦断开就掉到地上去了。

-
1
|
2
|
3
|
4
|
5

现在要把其中一个节点3往上移动一个位置。为了保证拆开扣住它的上一环之后，下面半截链条不掉到地上，所以首先要用手拿住要移动的节点3。

-
1
|
2
|
3 <- 抓住
|
4
|
5

之后把上面的 2扣住抓住的下面4

-
1
|
2
|
4 - 3 <- 抓住的
|
5

抓住的3扣住 2

-
1   3 <- 抓住的
| /
2
|
4
|
5

再用 1 扣住 3

-
1
|
3 <- 抓住的
|
2
|
4
|
5