leetcode [148]Sort List

你的名字 2021-12-07 14:21 290阅读 0赞

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

Example 1:

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

Example 2:

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

题目大意：

对链表进行排序

解法;

使用之前插排思想解决，待优化，效率较低。这里newHead的next为啥不用等于head呢？

因为算法具体的流程是如下的，相当于构造了两个list：

例如：

originally 1->3->2->null
helper: 0->null;
after the first loop:
original list :3->2->null
helper:0->1->null
after the second loop:
original list: 2->null
helper:0->1->3->null
after the third loop:
original list :null
helper:0->1->2->3-> null.

java:

  1. class Solution {
  2.     public ListNode sortList(ListNode head) {
  3.         if(head==null||head.next==null) return head;
  4.         ListNode newHead=new ListNode(-1);
  5.         ListNode pre=newHead;
  6.         ListNode cur=head;
  7.         while(cur!=null){
  8.             ListNode next=cur.next;
  9.             while(pre.next!=null&& pre.next.val<cur.val){
  10.                 pre=pre.next;
  11.             }
  12.             cur.next=pre.next;
  13.             pre.next=cur;
  14.             cur=next;
  15.             pre=newHead;
  16.         }
  18.         return newHead.next;
  19.     }
  20. }

　　

转载于:https://www.cnblogs.com/xiaobaituyun/p/10747173.html

发表评论

表情：
评论列表 （有 0 条评论，290人围观）

还没有评论，来说两句吧...

相关阅读