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

本文主要是介绍[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指向最后的headListNode cur = head; //将插入的结点ListNode pre = helper; //在pre和pre.next之间插入结点ListNode next = null; //下一个将被插入的结点//遍历原链表while( cur != null ){//保存下一个结点next = cur.next;//find the right place to insertwhile( pre.next != null && pre.next.val < cur.val ){pre = pre.next;}//将cur插入在pre 和 pre.next之间cur.next = pre.next;pre.next = cur;//pre归位helperpre = 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，会非常方便链表插入时的比较。

这篇关于[leetcode-排序]--147. Insertion Sort List的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---