LeetCodeMEDIM篇 Sort List

阅读: 评论:0

LeetCodeMEDIM篇 Sort List

LeetCodeMEDIM篇 Sort List

题目

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

十分钟思考

对于nlogn的时间复杂度,必定采用递归,折半,分而治之的思想。从list中间劈开,然后递归分割,排序后逐次合并。

但是写代码,不知道具体怎么写,看了其他人的实现,思路是对的,自己尝试写一遍。尤其是从中间分割list的方法,利用快慢指针,很厉害。一定要学会这个方法,之前判断单链表是否有环,也是利用快慢指针。来,自己写一下。代码一次通过,没有一点问题。总结一下:

1,拆分list的方法,利用快慢指针

2  合并两个单链表,从小到大排序。首先建立一个dummy node,作为新链表的开头,然后一个新的curr指针,指向加入的node

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode sortList(ListNode head) {//分而治之,从中间分开list//基准条件if(head==null||==null){return head;}ListNode fast=head;ListNode slow=head;ListNode pre=slow;while(fast!=null&&!=null){//记录断开位置pre=slow;slow&#;fast&#ext;}//断开=null;//递归拆分ListNode nodeLeft=sortList(head);ListNode nodeRight=sortList(slow);//合并list,需要依次拼接,刚开始各有一个节点,然后会有多个,依次往上合并return merge(nodeLeft,nodeRight);}private ListNode merge(ListNode l1,ListNode l2){//一个dummynode,一个curr指针,依次比较添加到新链表,长度不同,剩下的加入就可以ListNode dummy=new ListNode(0);ListNode curr;curr=dummy;while(l1!=null&&l2!=null){if(l1.val<l2.val){=l1;l1&#;}=l2;l2&#;}curr&#;}//如果长度不一样if(l1!=null){=l1;}if(l2!=null){=l2;};}}

 

本文发布于:2024-02-03 00:05:22,感谢您对本站的认可!

本文链接:https://www.4u4v.net/it/170688992347346.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

标签:LeetCodeMEDIM   Sort   List
留言与评论(共有 0 条评论)
   
验证码:

Copyright ©2019-2022 Comsenz Inc.Powered by ©

网站地图1 网站地图2 网站地图3 网站地图4 网站地图5 网站地图6 网站地图7 网站地图8 网站地图9 网站地图10 网站地图11 网站地图12 网站地图13 网站地图14 网站地图15 网站地图16 网站地图17 网站地图18 网站地图19 网站地图20 网站地图21 网站地图22/a> 网站地图23