Java for LintCode 链表插入排序

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

用插入排序对链表排序

解题思路：

最省时间的方法是使用优先级队列，但是无法通过，那就直接插入排序好了。

    public ListNode insertionSortList(ListNode head) {

		ListNode root = new ListNode(Integer.MIN_VALUE);

		while (head != null) {

			ListNode temp = root;

			while (temp.next != null && head.val >= temp.next.val)

				temp = temp.next;

			if(temp.next==null){

				temp.next=head;

				head=head.next;

				temp.next.next=null;

			}

			else{

				ListNode temp2 = temp.next;

				temp.next=head;

				head=head.next;

				temp.next.next=temp2;

			}

		}

		return root.next;

    }