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