如何使用（双）指针来更新其他指针的值

Question

我正在尝试将一组单独排序的链表合并到一个排序的链表中（顺便说一句，这是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;
    }

在函数的最后，我想在具有最小元素的链表中前进。但是，我的代码仅更改了 poninter 值

*pSmallest

，而不影响

pSmallest

指向的链表节点。如何在

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;
    }
    // ...

虽然这确实将输入列表中最小节点的值绑定到

pSmallest

并因此更新输入链表中的相应节点，但它也会在下一个循环迭代中更改其值，我试图在其中将

pSmallest

重新初始化为输入列表中的下一个最小节点。

Answer 1

通过分配给

*pSmallest

，您不会更新

lists

中的条目，并且在第二次尝试中，

&plist

也是一个与

lists

不相关的地址，但在一个循环的迭代。所以这也是不对的。

您可以只使用索引

i

，您必须记住哪个列表具有最小值，并使用它来更新

lists

中的条目：

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

    while (true) {
        int iSmallest = -1;

        // find smallest node value
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] && (iSmallest < 0 || lists[i]->val < lists[iSmallest]->val)) {
                iSmallest = i;
            }
        }
        if (iSmallest < 0) break; // All done
        // append smallest node to merged list
        current = current->next = lists[iSmallest];
        // Remove it from the list we took it from 
        lists[iSmallest] = lists[iSmallest]->next;
    }

    return head->next;
}

请注意，这不是一个有效的解决方案。

lists

中的条目数量可能很大，然后遗憾的是必须迭代所有条目以找到其中的最小值......一遍又一遍。

为了改进这一点，有多种方法，例如分而治之（一次合并 2 个列表）或使用优先级队列（堆）。