【leetcode hot 100 148】排序序列

解法一：（双重循环）第一个循环head，逐步将head的node加入有序列表；第二个循环在有序列表中找到合适的位置，插入node。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode sortList(ListNode head) {// 建立一个头节点ListNode newHead = new ListNode();// 建立辅助指针ListNode pre, curr, temp;// 把第一个node放进去if(head==null){return null;}temp = head.next;newHead.next = head;head.next = null;head = temp;// 循环while(head != null){pre = newHead;curr = newHead.next;while(curr.val<head.val){pre = pre.next;curr = curr.next;if(curr==null){break;}}temp = head.next;head.next = curr;pre.next = head;head = temp;}return newHead.next;}
}

注意：

• 要在第二个循环内判断curr==null，不能在第二个循环while()中判断。即curr==null的判断要先于curr.val<head.val判断。
• 在使用head.next之前，要先判断head==null。

错误原因：

解法二：自顶向下归并排序

对链表自顶向下归并排序的过程如下：

• 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
• 对两个子链表分别排序。
• 将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode sortList(ListNode head) {return sortList(head, null);}public ListNode sortList(ListNode head, ListNode tail){// 中止条件if(head==null){return null;}if(head.next==tail){head.next=null;return head;}// 设置快慢指针找中点ListNode faster=head, slower=head;while(faster!=tail){faster=faster.next;slower=slower.next;if(faster!=tail){faster=faster.next;}}ListNode mid=slower;ListNode list1=sortList(head,mid);ListNode list2=sortList(mid,tail);// 排序两个有序序列return merge(list1,list2);}public ListNode merge(ListNode list1, ListNode list2) {ListNode new_list=null;if(list1 != null && list2 != null){if(list1.val<=list2.val){new_list=list1;list1=list1.next;new_list.next=null;}else{new_list=list2;list2=list2.next;new_list.next=null;}}else{return list1!=null?list1:list2;}ListNode curr=new_list;while(list1 != null && list2 != null){if(list1.val<=list2.val){ListNode temp = list1.next;curr.next=list1;list1.next=null;list1=temp;}else{ListNode temp = list2.next;curr.next=list2;list2.next=null;list2=temp;}curr=curr.next;}if(list1!=null){curr.next=list1;}if(list2!=null){curr.next=list2;}return new_list;}
}

注意：

• 中止条件：head==null和head.next==tail
• faster走第二步的时候也要判断faster!=tail