LeetCode148.排序链表

链表"/>

LeetCode148.排序链表

看完题目的想法是，直接把所有节点的值都遍历出来放进优先队列里面，然后从头节点遍历一次，每次把优先队列poll()的值赋给节点的val即可，说实话，想完还觉得估计有问题怎么可能这么简单，但是不管了，5分钟就把这个算法写出来了，一提交，居然通过了！以下是我的代码：

class Solution {public ListNode sortList(ListNode head) {PriorityQueue<Integer> pri = new PriorityQueue<>(new Comparator<Integer>(){public int compare(Integer e1, Integer e2){return e1 - e2;}});ListNode h = head;while(h != null){pri.add(h.val);h = h.next;}ListNode h2 = head;while(h2 != null){h2.val = pri.poll();h2 = h2.next;}return head;}

其实这个优先队列也不用new一个比较器实例，因为默认是从小到大的。然后看看官方题解吧，不要用我这种二流子写法了。

题解用的是归并排序，先把链表分成两半，每半分别排序，然后再把排完序的两半合并起来；对于两半中的每一半也是这样的，把这半再分成两半，两半分别排好序合起来，只有当“一半”只有两个节点是不用再分，直接比较这两个节点然后排序，然后再与另一半合起来，然后再与更大的另一半合起来...一直合到这个完整的最大的链表。

分割可以采用快慢指针的方法，快慢指针同时从头节点出发，快指针每次走两步，慢指针每次走一步，当快指针到达链尾，慢指针就在中间节点。然后利用递归的方法不断的分割链表，直到只剩两个节点，开始合并。

合并先创建一个哑节点，然后分别比较左右两个链表的头节点，最小的先移到哑节点后面，然后这个链表的指针移到下一个节点，下次比较就是这个链表的第2个节点和另一个链表的第一个节点，（因为两个链表都是已经排好序的，所以每次只要比较两个链表未放进去的最小节点即可），如果一个链表已经遍历完了，只要把另一个链表剩下的部分直接挂在后面即可。

以下是题解代码：

class Solution {public ListNode sortList(ListNode head) {return sortList(head, null);}public ListNode sortList(ListNode head, ListNode tail) {if (head == null) {return head;}if (head.next == tail) {head.next = null;return head;}ListNode slow = head, fast = head;while (fast != tail) {slow = slow.next;fast = fast.next;if (fast != tail) {fast = fast.next;}}ListNode mid = slow;ListNode list1 = sortList(head, mid);ListNode list2 = sortList(mid, tail);ListNode sorted = merge(list1, list2);return sorted;}public ListNode merge(ListNode head1, ListNode head2) {ListNode dummyHead = new ListNode(0);ListNode temp = dummyHead, temp1 = head1, temp2 = head2;while (temp1 != null && temp2 != null) {if (temp1.val <= temp2.val) {temp.next = temp1;temp1 = temp1.next;} else {temp.next = temp2;temp2 = temp2.next;}temp = temp.next;}if (temp1 != null) {temp.next = temp1;} else if (temp2 != null) {temp.next = temp2;}return dummyHead.next;}
}