萤火小屋

优律的知识库

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

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

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

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

题目描述

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

样例

  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中序遍历题解
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

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