力扣23题-合并K个升序链表-分治题解分析

题目描述

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

样例

1. 样例1：
   输入：lists = [[1,4,5],[1,3,4],[2,6]]
   输出：[1,1,2,3,4,4,5,6]
   解释：链表数组如下：
   [
   1->4->5,
   1->3->4,
   2->6
   ]
   将它们合并到一个有序链表中得到。
   1->1->2->3->4->4->5->6

2. 样例2：
   输入：lists = []
   输出：[]

3. 样例3：
   输入：lists = [[]]
   输出：[]

题目评估

知识点：链表、分治算法
难度：困难

分析

如果只有两个顺序链表，把他们合并成一个顺序链表，这样的题目我们大家都会，那么现在有若干个链表，我们把他们合并成一个链表我们就会一脸懵逼。这时候采用分治算法，把这若干个链表分化成只有两个链表的问题，那么我们处理两个链表就如鱼得水了！代码如下，关键处有注释。

Java代码题解

//import java.util.Arrays;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

	public ListNode mergeKLists(ListNode[] lists) {
        
		if (lists.length == 1) {  // 如果长度等于1，直接返回那个唯一链表
			return lists[0];
		}
		
		if (lists.length == 0) {  // 如果长度为0，返回null
			return null;
		}
		
        int mid = lists.length / 2;  // 找到中点，然后分治
        // 分治
        ListNode leftList = mergeKLists(Arrays.copyOf(lists, mid));  // 递归中点左侧
        ListNode rightList = mergeKLists(Arrays.copyOfRange(lists, mid, lists.length));  // 递归中点右侧
        ListNode resListHead = new ListNode();  // 定义一个结果链表的头节点，方便后边指针后移，注意返回的时候要返回头节点的next
        resListHead.next = null;  // 这里给head的next赋一个null
        
        // 定义三个指针：分别是左链表指针，右链表指针，和结果链表指针
        ListNode leftPointer = leftList, rightPointer = rightList, resPointer = resListHead;
        while (leftPointer != null && rightPointer != null) {  // 同时遍历两个链表，比较填充给结果链表
        	if(leftPointer.val < rightPointer.val) {  // 比较一下，谁小谁接在结果链表下边
        		resPointer.next = leftPointer;
        		leftPointer = leftPointer.next;
        		resPointer = resPointer.next;
        	} else {
        		resPointer.next = rightPointer;
        		rightPointer = rightPointer.next;
        		resPointer = resPointer.next;
        	}
        }
        
        if (leftPointer != null) {  // 如果左链表剩下了，就把它全都接在结果链表下边
        	resPointer.next = leftPointer;
        }
        
        if (rightPointer != null) {  // 如果右链表剩下了，就把它全都接在结果链表下边
        	resPointer.next = rightPointer;
        }
   
        return resListHead.next;
    }
}

力扣23题

复杂度分析

递归遍历，在合并链表时是顺序的所以时间复杂度：O(n)
递归遍历使用栈空间并且有辅助的链表，空间复杂度：O(n)