LeetCode 147 對連結清單進行插入排序

題目描述：

對連結清單進行插入排序。

插入排序的動畫示範如上。從第一個元素開始，該連結清單可以被認為已經部分排序（用黑色表示）。

每次疊代時，從輸入資料中移除一個元素（用紅色表示），并原地将其插入到已排好序的連結清單中。

插入排序算法：

1. 插入排序是疊代的，每次隻移動一個元素，直到所有元素可以形成一個有序的輸出清單。
2. 每次疊代中，插入排序隻從輸入資料中移除一個待排序的元素，找到它在序列中适當的位置，并将其插入。
3. 重複直到所有輸入資料插入完為止。

示例：

輸入：4 → 2 → 1 → 3

輸出：1 → 2 → 3 → 4

輸入：-1 → 5 → 3 → 4 → 0

輸出：-1 → 0 → 3 → 4 → 5

個人解法：

當連結清單為空或隻有一個節點時，直接傳回

将連結清單第一個節點的 next 置空，将這一部分看作有序連結清單，并從第二個節點開始，插入到前面有序連結清單的适當位置，對于适當位置的查找，從連結清單頭節點處開始周遊，用一前一後兩個指針儲存，後面的指針用于比較值大小，當值大小恰當時，前指針恰好為插入位置的前驅節點，将節點插入即可

由于将節點插入到有序連結清單中，該節點後面的節點便會丢失，故在插入前需要使用一個指針 next 指向待插入節點的後繼節點，而當周遊到連結清單的最後一個節點時，不需要再儲存該後繼節點

public ListNode insertionSortList(ListNode head) {
	if (head == null || head.next == null) {
		return head;
	}
	ListNode result = new ListNode(0, head);
	ListNode cur = head.next;
	ListNode next = cur.next;
	head.next = null;
	ListNode pre = result;
	ListNode temp = head;
	while (cur != null) {
		if (temp != null && temp.val < cur.val) {
			pre = pre.next;
			temp = temp.next;
		} else {
			pre.next = cur;
			cur.next = temp;
			if (next == null) {
				break;
			}
			cur = next;
			next = cur.next;
			pre = result;
			temp = result.next;
		}
	}
	return result.next;
}
           

官方解法：

對連結清單進行插入排序的具體過程如下。

1. 首先判斷給定的連結清單是否為空，若為空，則不需要進行排序，直接傳回。
2. 建立啞節點 dummyHead，令 dummyHead.next = head。引入啞節點是為了便于在 head 節點之前插入節點。
3. 維護 lastSorted 為連結清單的已排序部分的最後一個節點，初始時 lastSorted = head。
4. 維護 curr 為待插入的元素，初始時 curr = head.next。
5. 比較 lastSorted 和 curr 的節點值。
6. 若 lastSorted.val <= curr.val，說明 curr 應該位于 lastSorted 之後，将 lastSorted 後移一位，curr 變成新的 lastSorted。否則，從連結清單的頭節點開始往後周遊連結清單中的節點，尋找插入 curr 的位置。令 prev 為插入 curr 的位置的前一個節點，進行如下操作，完成對 curr 的插入：
7. 令 curr = lastSorted.next，此時 curr 為下一個待插入的元素。
8. 重複第 5、6、7 步，直到 curr 變成空，排序結束。
9. 傳回 dummyHead.next，為排序後的連結清單的頭節點。

public ListNode insertionSortList1(ListNode head) {
	if (head == null) {
		return head;
	}
	ListNode dummy = new ListNode(0, head);
	ListNode lastSorted = head, curr = head.next;
	while (curr != null) {
		if (lastSorted.val <= curr.val) {
			lastSorted = lastSorted.next;
		} else {
			ListNode prev = dummy;
			while (prev.next.val <= curr.val) {
				prev = prev.next;
			}
			lastSorted.next = curr.next;
			curr.next = prev.next;
			prev.next = curr;
		}
		curr = lastSorted.next;
	}
	return dummy.next;
}