当前位置: 首页 > article >正文

LeetCode 解题思路 17(Hot 100)

在这里插入图片描述

解题思路:

  1. 找到链表中点: 使用快慢指针法,快指针每次移动两步,慢指针每次移动一步。当快指针到达末尾时,慢指针指向中点。
  2. 递归分割与排序: 将链表从中点处分割为左右两个子链表,分别对这两个子链表递归排序。
  3. 合并有序子链表: 将两个已排序的子链表合并成一个有序链表。

Java代码:

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next; 
        slow.next = null;
        
        ListNode left = sortList(head);
        ListNode right = sortList(mid);
        
        return merge(left, right);
    }
    
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        
        current.next = (l1 != null) ? l1 : l2;
        
        return dummy.next;
    }
}

复杂度分析:

  • 时间复杂度: 归并排序的时间复杂度为 ​O(nlogn)。
  • 空间复杂度: O(log n)​。(递归栈深度)

在这里插入图片描述

解题思路:

  1. 初始化优先队列: 将所有链表的头节点加入堆中,堆顶元素为当前最小值。
  2. 构建结果链表: 每次从堆顶取出最小节点,添加到结果链表中,并将其下一个节点加入堆中(若存在)。
  3. 处理空链表: 跳过输入数组中的空链表,避免无效操作。

Java代码:

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
        
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }
        
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        
        while (!minHeap.isEmpty()) {
            ListNode smallest = minHeap.poll();
            current.next = smallest;
            current = current.next;
            
            if (smallest.next != null) {
                minHeap.offer(smallest.next);
            }
        }
        
        return dummy.next;
    }
}

复杂度分析:

  • 时间复杂度: O(nklogk),其中 n 是总节点数,k 是链表数量。
  • 空间复杂度: O(k),用于存储堆中的节点。

http://www.kler.cn/a/587370.html

相关文章:

  • Android 自定义数字键盘实现教程
  • POCO F4刷机color 15
  • WSL2 Ubuntu安装GCC不同版本
  • 剑指 Offer II 087. 复原 IP
  • 计算机:基于深度学习的Web应用安全漏洞检测与扫描
  • kong搭建一套微信小程序的公司研发环境
  • 编译OpenSSL
  • 机器学习 : 训练过程
  • 1688按图搜索商品(拍立淘)接口的参数说明【附代码实例】
  • 77.HarmonyOS NEXT ImageViewerView 组件深度剖析: Swiper容器与懒加载深度解析
  • OpenBMC:BmcWeb添加路由1 getParameterTag
  • AI 直播盈利全攻略:借助智能技术实现收入自动化增长
  • 工厂方法模式 (Factory Method Pattern)
  • /proc/sys/kernel/yama/ptrace_scope的作用
  • 使用某个软件出现白屏测试员该如何排查原因?
  • 自动化测试-网页聊天室
  • Project回调函数qsort②进阶应用
  • 深度学习基础:线性代数本质6——逆矩阵、列空间与零向量
  • 滑动窗口[判断子集是否满足条件] 力扣:209 ▎2962 ▎3306
  • 图片加载框架Glide与Picasso原理剖析