LeetCode 腾讯精选50题--合并K个排序链表

快来打我* 2023-06-05 05:53 9阅读 0赞

今天的题目稍微有点复杂了，因为是K个有序链表的合并，看到这道题后的大体思路是这样的：

1.首先先做到两个链表的合并，链表的合并我想到的是用递归操作，

2.其次是多个链表的合并，所以在第一步实现的基础上，我考虑每次选择两个链表进行合并，一个链表数组作为一个整体，那么就可以采用归并算法进行合并，利用两个指针分别指向当前的数组位置，不断切分直到指针指向一个位置，再返回，然后进行合并，由于递归的操作，可以保证每次合并时只会有两个排序好的链表。

所以这辆的关键就是要搞清楚怎么递归去合并两个链表，以及如何递归合并一个大的数组

如下是代码：

1 package algorithm;
     2 
     3 public class RecursiveSort {
     4 
     5     public ListNode mergeKLists(ListNode[] lists) {
     6         if(lists.length < 1){
     7             return null;
     8         }
     9 
    10         return merge(lists,0,lists.length-1);
    11     }
    12 
    13     private ListNode merge(ListNode[] lists,int left,int right){
    14 
    15         if(left >= right){
    16             return lists[left];
    17         }
    18         int center = (left+right)/2;
    19 
    20         ListNode leftNode = merge(lists,left,center);
    21         ListNode rightNode = merge(lists,center+1,right);
    22 
    23         ListNode temp = new ListNode();
    24         temp = mergeTwoListNode2(leftNode,rightNode,temp);
    25 
    26         return temp;
    27 
    28     }
    29 
    30     /**
    31      * 递归合并
    32      * @param l1
    33      * @param l2
    34      * @param temp
    35      * @return
    36      */
    37     private ListNode mergeTwoListNode2(ListNode l1,ListNode l2,ListNode temp){
    38         if(l1 == null || l2 == null){
    39             if(l1 == null && l2 == null){
    40                 return l1; //边界情况返回哪个都是可以的
    41             }else {
    42                 temp = l1 == null ? l2 : l1;
    43             }
    44 
    45             return temp;
    46         }
    47 
    48         if(l1.val > l2.val){ 
    49             temp = l2;
    50             temp.next = mergeTwoListNode2(l1,l2.next,temp.next);
    51         }else {
    52             temp = l1;
    53 
    54             temp.next = mergeTwoListNode2(l1.next,l2,temp.next);
    55         }
    56 
    57         return temp;
    58 
    59     }
    60 
    61 }

最后说实话，对于递归我还是没有搞明白，这道题也算是稀里糊涂的就完成了，但是个人认为比较重要的一点是先做好简单的，也就是先把两个链表的合并解决了，那剩下多个链表的合并就可以转变为多次 两个链表的合并这一步骤

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