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;
}