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

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