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个升序链表
评论区