萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

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

发表于 2021-03-30 | 分类于 力扣刷题 | 0 | 阅读次数 183

题目描述

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

样例

  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)

# 算法 # 程序设计 # Java # 分治算法
分治算法
力扣98题-验证二叉搜索树-DFS中序遍历题解
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

67 日志
17 分类
41 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2022 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持