LeetCode | Insertion Sort List

题目

Sort a linked list using insertion sort.

分析

题目已经明确说了用插入排序，由于是链表，无法像数组那样从后往前依次比较插入，只能从前往后了。

在链表首部添加一个哨兵可以稍微简化下代码。

代码

public class InsertionSortList {
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}

	public ListNode insertionSortList(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}

		// dummy
		ListNode dummy = new ListNode(Integer.MIN_VALUE);
		dummy.next = head;

		ListNode qPre = head;
		ListNode q = head.next;
		while (q != null) {
			ListNode next = q.next;
			if (q.val < qPre.val) {
				ListNode pPre = dummy;
				ListNode p = dummy.next;
				while (!p.equals(q)) {
					if (q.val < p.val) {
						// cut
						qPre.next = next;
						// paste
						q.next = pPre.next;
						pPre.next = q;
						break;
					}
					pPre = p;
					p = p.next;
				}
			} else {
				qPre = q;
			}
			q = next;
		}

		return dummy.next;
	}
}