147. Insertion Sort List 发表于 2022-07-17 Two Pointers1234567891011121314151617181920212223242526272829303132class Solution { public ListNode insertionSortList(ListNode head) { ListNode dummyHead = new ListNode(Integer.MIN_VALUE, head); ListNode orderedTail = head, curr = head.next; // orderedTail 可以从 head 开始,不必从 dummyHead 开始。在整个驱动过程中,orderedTail 与 curr 紧挨并同步移动 while (curr != null) { if (curr.val >= orderedTail.val) { orderedTail = curr; curr = curr.next; } else { // 需要将 curr 节点插入到之前已排序的链表中 ListNode next = curr.next; // 将 curr 从链表中摘除 orderedTail.next = next; // 找到插入点进行插入 ListNode pre = dummyHead; while (pre.next.val < curr.val) { pre = pre.next; } // now: pre.next.val >= curr.val curr.next = pre.next; pre.next = curr; curr = next; } } return dummyHead.next; }} Reference147. Insertion Sort List