[leetcode-排序]--147. Insertion Sort List

Question147. Insertion Sort List

Sort a linked list using insertion sort.

中文：使用插入排序来让链表有序。

解决思路：在新链表的head结点之前构建一个结点，然后将所有的结点依次插入在helper结点之后，最后返回helper.next 结点即是排序后的新链表的首结点。

实现源码：

/** * 核心思想是在head前面构造一个helper结点 * @param head * @return */ public static ListNode insertionSortList2(ListNode head) { if( head == null ){ return head; } ListNode helper = new ListNode(0); //构造一个结点, 该节点不算入实际的数据链表中,仅仅把其next指向最后的head ListNode cur = head; //将插入的结点 ListNode pre = helper; //在pre和pre.next之间插入结点 ListNode next = null; //下一个将被插入的结点 //遍历原链表 while( cur != null ){ //保存下一个结点 next = cur.next; //find the right place to insert while( pre.next != null && pre.next.val < cur.val ){ pre = pre.next; } //将cur插入在pre 和 pre.next之间 cur.next = pre.next; pre.next = cur; //pre归位helper pre = helper; //cur后移 cur = next; } return helper.next; }

上诉排序的时间复杂度不难分析得出是O(n^2)。

测试用例：

public static void main(String[] args) { ListNode head = new ListNode(0); ListNode n1 = new ListNode(2); ListNode n2 = new ListNode(4); ListNode n3 = new ListNode(1); ListNode n4 = new ListNode(3); head.next = n1; n1.next = n2; n2.next=n3; n3.next=n4; ListNode h = insertionSortList2(head); while (h!=null){ System.out.println(h.val); h = h.next; } }

输出：

0,1,2,3,4,

从这题里面学到的思路：

对于链表的插入，可以试着构造一个虚拟的结点作为head的前结点，这样无形中就给head构造了一个前结点pre，会非常方便链表插入时的比较。