[LeetCode] 147. Insertion Sort Listjava

/**147. Insertion Sort List * @param head * @return 链表，使用插入排序 */ public ListNode insertionSortList(ListNode head) { if (head == null) return head; ListNode ret = new ListNode(Integer.MIN_VALUE); ret.next = head; ListNode pre = head; ListNode cur = head.next; while (cur != null) { if (cur.val < pre.val) { ListNode next = cur.next; for (head = ret; head != cur; head = head.next) { if (cur.val >= head.val && cur.val < head.next.val) { pre.next = cur.next; cur.next = head.next; head.next = cur; } } cur = next; } else { pre = cur; cur = cur.next; } } return ret.next; }

ret指向返回的表头 cur是现在处理的节点，pre为前一个节点 cur从head的下一个节点开始处理，如果cur>pre,说明需要插入： 保存下一个将要处理的节点为next 从头开始找到插入点：if (cur.val >= head.val && cur.val < head.next.val)

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

sorted list是空，把一个元素插入sorted list中。然后，在每一次插入过程中，都是找到最合适位置进行插入。 pre始终指向sorted list的fakehead，cur指向当前需要被插入的元素，next指向下一个需要被插入的元素。 当sortedlist为空以及pre.next所指向的元素比cur指向的元素值要大时，需要把cur元素插入到pre.next所指向元素之前。否则，pre指针后移。最后返回fakehead的next即可。