侧边栏壁纸
博主头像
阿里灰太狼博主等级

You have to believe in yourself . That's the secret of success.

  • 累计撰写 104 篇文章
  • 累计创建 50 个标签
  • 累计收到 12 条评论

目 录CONTENT

文章目录

leetcode-23. 合并K个升序链表

阿里灰太狼
2021-12-09 / 0 评论 / 0 点赞 / 189 阅读 / 1,588 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2021-12-09,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

cj91.pngcj92.png

JAVA解法

/**
 * 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) {
        // 定义一个维护最终答案的 ans 链表
        ListNode ans = null;
        // 遍历 lists 中的所有链表
        for (int i = 0; i < lists.length; ++i) {
            // 其中两两合并
            ans = mergeTwoLists(ans, lists[i]);
        }
        // 返回最终合并完的答案
        return ans;
    }
    // 实现两两合并的逻辑
    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        // 只要有一个链表为空则返回另一个
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        // 定义一个值为 0 的头节点
        ListNode head = new ListNode(0);
        // 定义 tail 结点并让头节点指向它,定义两个分别指向传进的两链表的指针节点
        ListNode tail = head, aPtr = a, bPtr = b;
        // 只有连个指针节点不为空的时候进行遍历
        while (aPtr != null && bPtr != null) {
            // 两两值的比较并把 tail.next 指向较小的那个
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                // 因为此时较小的已经存进去了,维护指针位置为原 aPtr 的下一个
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                // 因为此时较小的已经存进去了,维护指针位置为原 bPtr 的下一个
                bPtr = bPtr.next;
            }
            // 因为 tail 已经更新所以要维护 tail 的位置为原 tail 的下一个
            tail = tail.next;
        }
        // 若 aPtr == null 则证明 aPtr 到尽头了,则接上 bPtr 即可,反之同理
        tail.next = (aPtr != null ? aPtr : bPtr);
        // 最后返回
        return head.next;
    }
}

题解分析

这道题合并多个有序链表,结合之前做过的合并两个有序链表,这道题可以被拆成一个主线:遍历所有存在的链表,一个支路:用双指针合并合并两个有序链表。

首先,在主线中定义一个维护最终答案的 ans 链表,然后遍历 lists 中的所有链表,其中进入支路让链表两两合并,合并完则返回。

支路逻辑:传进来的两个链表只要有一个链表为空则返回另一个。定义一个虚拟的头节点值为 0,定义 tail 结点并让头节点指向它,定义两个分别指向传进的两链表的指针节点,只有连个指针节点不为空的时候进行遍历。两指针节点所在的节点值两两值的比较并把 tail.next 指向较小的那个,同时那个较小那个的节点已经被使用,所以要让其赋值为下一个节点,此时分的 taill 同理也要维护。

到此已经完成相同长度的合并了,若 aPtr == null 则证明 aPtr 到尽头了,则接上 bPtr 即可,反之 aPtr != null 则并上 aPtr,因为上面的循环条件是 aPtr != null && bPtr != null,就是因为有一方为空才结束循环,但仍然还有一个链表剩下没合并的部分,因为是有序的,所以直接合并即可。

做题感想

第一次接触 hard 题,还是费了不少时间,一道题近一个钟,还是感觉到了 hard 题的威力了,但是看评论这道题还是 hard 题里边算简单的了,还要再接再厉。

leetcode原题:23. 合并K个升序链表

0

评论区