如何用二级指针更新指针值？合并K个排序链表实现疑问

这是LeetCode第23题的场景：合并多个已排序的单链表为一个排序链表。链表定义如下：

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

问题描述 #

你当前的实现尝试每次找出所有链表中最小的节点，将其加入合并后的链表，然后推进对应链表的指针，但最后一行推进指针的操作并未影响原链表：

ListNode* mergeKLists(vector<ListNode*> &lists) {
    ListNode *head = new ListNode(-1);
    ListNode *current = head;

    while (find_if(lists.begin(), lists.end(), [](ListNode *node) { return node; }) != lists.end()) {
        ListNode **pSmallest = nullptr;

        // find smallest node value
        for (int i = 0; i < lists.size(); i++) {
            ListNode *plist = lists.at(i);
            if (!plist) continue;
            if (!pSmallest) {
                pSmallest = new ListNode*;
                *pSmallest = plist;
            }
            else if (plist->val < (*pSmallest)->val) *pSmallest = plist;
        }

        // append smallest node to merged list
        current->next = *pSmallest;
        current = current->next;

        // advance in list with smallest node
        *pSmallest = (*pSmallest)->next;
        // ^^^^^^^^ this line does not do what I would expect
    }

    return head->next;
}

你尝试过用引用实现，但会导致下一次循环无法正确初始化pSmallest：

// ...
// find smallest node value
for (int i = 0; i < lists.size(); i++) {
    ListNode *plist = lists.at(i);
    if (!plist) continue;
    if (!pSmallest) {
        pSmallest = &plist;
    }
    else if (plist->val < (*pSmallest)->val) pSmallest = &plist;
}
// ...

问题根源 #

1. 第一种方法里，你new了一个独立的ListNode*指针，它和输入vector里的指针没有关联，修改*pSmallest只会改变这个新指针的值，完全不影响原链表的指针。
2. 第二种方法里，你取的是局部变量plist的地址——plist只是lists[i]的副本，修改*pSmallest只会改变这个局部副本，原vector里的指针不会更新；而且plist是栈上变量，循环结束后地址失效，后续操作会有风险。

正确解法 #

核心是让pSmallest直接指向vector中存储的指针的地址（也就是&lists[i]），这样修改*pSmallest时，就是直接修改vector里的原指针，从而正确推进对应链表。

修改后的完整代码：

ListNode* mergeKLists(vector<ListNode*> &lists) {
    ListNode *head = new ListNode(-1);
    ListNode *current = head;

    while (find_if(lists.begin(), lists.end(), [](ListNode *node) { return node; }) != lists.end()) {
        ListNode **pSmallest = nullptr;

        // 遍历vector，直接操作原指针的地址
        for (int i = 0; i < lists.size(); i++) {
            // 跳过已空的链表
            if (!lists[i]) continue;
            // 初始化最小指针，直接指向vector中的元素地址
            if (!pSmallest) {
                pSmallest = &lists[i];
            }
            // 比较当前链表节点值，更新最小指针的指向
            else if (lists[i]->val < (*pSmallest)->val) {
                pSmallest = &lists[i];
            }
        }

        // 将最小节点加入合并链表
        current->next = *pSmallest;
        current = current->next;

        // 推进原链表的指针——这里修改的是vector里的原指针，正确生效
        *pSmallest = (*pSmallest)->next;
    }

    return head->next;
}

关键说明 #

• pSmallest存储的是vector中某个ListNode*的地址（&lists[i]），所以*pSmallest就是lists[i]本身。
• 执行*pSmallest = (*pSmallest)->next时，直接修改了lists[i]的值，让它指向原链表的下一个节点，这样下一轮循环就能正确处理剩余的节点。

内容的提问来源于stack exchange，提问作者Tim