济南建设网站公司哪个好,设计网名姓氏,如何做网页宣传,免费h5场景制作软件看完题目的想法是#xff0c;直接把所有节点的值都遍历出来放进优先队列里面#xff0c;然后从头节点遍历一次#xff0c;每次把优先队列poll()的值赋给节点的val即可#xff0c;说实话#xff0c;想完还觉得估计有问题怎么可能这么简单#xff0c;但是不管了#xff0c… 看完题目的想法是直接把所有节点的值都遍历出来放进优先队列里面然后从头节点遍历一次每次把优先队列poll()的值赋给节点的val即可说实话想完还觉得估计有问题怎么可能这么简单但是不管了5分钟就把这个算法写出来了一提交居然通过了以下是我的代码
class Solution {public ListNode sortList(ListNode head) {PriorityQueueInteger pri new PriorityQueue(new ComparatorInteger(){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;}
}
