==========================努力奋斗财源广进==========================

一、算法题目

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

二、题解

1、我的题解

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    //两个链表合并函数
    public ListNode Merge(ListNode list1, ListNode list2) { 
       
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while((list1 != null) && (list2 != null)){
            if(list1.val > list2.val){
                cur.next = list2;
                list2 = list2.next;
            }else{
                cur.next = list1;
                list1 = list1.next;
            }
            cur = cur.next;
        }
        if(list1 != null){
            cur.next = list1;
        } else if(list2 != null){
            cur.next = list2;
        }
        return head.next;
    }
    
    //撰写函数
    ListNode divedList(ArrayList<ListNode> list, int left, int right){
        if(left > right){
            return null;
        } else if(left == right){
            return list.get(left);
        }
        int mid = (left + right) / 2;
        return Merge(divedList(list,left,mid),divedList(list,mid+1,right));
    }
    
     public ListNode mergeKLists(ArrayList<ListNode> lists) {
        //k个链表归并排序
        return divedList(lists, 0, lists.size() - 1);
    }
}

解法的比较简单，就是使用了递归的思想。

递归的是将K个链表进行对半划分，直到划分成最小的两个链表，然后再进行合并。

使用递归最重要的是注意递归几大事项。

首当其中的应该是递归的终止条件

终止条件： 左边大于右边，或者左右两边相等

如果条件满足的话，这里指的左右两边相等，就返回一个链表。

返回条件： 一个链表

每层执行的任务是啥？

执行任务： 把K个链表进行划分最小单位，划分为最小单位后再进行合并。

合并的需要另一个函数，就是简单的把两个链表按照最小值进行合并。

2、优秀题解

//待定

三、解法心得

四、自我监督

评论区记录复习记录