LeetCode 腾讯精选50题--链表排序

柔情只为你懂 2023-06-05 05:53 0阅读 0赞

解题思路：归并

先把链表拆开，分为两部分，一直拆到只剩一个元素后，进行合并，利用一个临时节点记录重排后的链表的起始位置

合并不难，困难点在于如何拆分链表，自己的大体思路是利用两个指针，一个一次移动两位，一个移动一位，当移动快的结束时，慢的指针指向的位置就是链表的中间位置，

将中间位置往后的进行递归切割，然后将中间位置的下一个指针指向空，即断开链表，再对左边的子链进行递归。

边界条件就是当中间位置与起始位置重合时，就返回起始链表

代码如下：

1 package algorithm;
     2 
     3 import basic.ListNode;
     4 
     5 public class SortLinkList {
     6 
     7     public ListNode sortList(ListNode head) {
     8 
     9         return sort(head,null);
    10     }
    11 
    12 
    13     private ListNode sort(ListNode head,ListNode middle) {
    14 
    15         if(head == null && middle == null){
    16             return null;
    17         }
    18         if(head == middle){
    19             return head;
    20         }
    21         ListNode fast = head;
    22         ListNode slow = head;
    23         while (fast != null && fast != middle && fast.next != middle){
    24             fast = fast.next.next;
    25             slow = slow.next;
    26         }
    27 
    28         ListNode subNode = slow;
    29         ListNode r = sort(slow.next,middle);
    30 
    31         subNode.next = null;
    32         ListNode l = sort(head,subNode);
    33 
    34         return merge(l,r);
    35     }
    36 
    37     private ListNode merge(ListNode left ,ListNode right){
    38 
    39         ListNode temp = new ListNode(0);
    40         ListNode record = temp;
    41         while (left != null && right!= null){
    42             if(left.val < right.val){
    43                 record.next = left;
    44                 left = left.next;
    45 
    46             }else {
    47                 record.next = right;
    48                 right = right.next;
    49             }
    50             record = record.next;
    51         }
    52         if(left != null){
    53             record.next = left;
    54         }else if(right!= null){
    55             record.next = right;
    56         }
    57         return temp.next;
    58     }
    59 
    60 
    61 }

但是由于只使用了一个空节点用于记录链表，所以空间复杂度为O(1) ，由于使用归并，时间复杂度为O(NlogN)。

转载于:https://www.cnblogs.com/Kaithy-Rookie/p/11329123.html