归并K排序LinkedLists中的循环

Question

我的合并k-排序列表算法使用分而治之的方法，并在过程中使用合并2列表算法作为辅助。

问题在于，在迭代过程中创建了一个循环，而我不知道为什么。

我追踪到了发生这种情况的确切位置的代码，但我仍然无法识别问题所在。

class Solution {
public:

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2, bool debug=false) 
    {
        ListNode *head = new ListNode(-1);
        ListNode *curr = head;

        while(l1 && l2) 
        {   

          if(l1->val <= l2->val)
            {
                curr->next = l1;
                l1 = l1->next;
            }
            else
            {
                curr->next = l2; 
                l2 = l2->next;

            }
            curr = curr->next;

        }
        // some list may be still populated
        l1 != NULL ? curr->next = l1 : curr->next = l2;
        return head->next;
    }


    ListNode* mergeKLists(std::vector<ListNode*>& lists) 
    {
        // approach of divide and conquer
        int size = lists.size();
        int interval = 1;
        int tmp_val = 1;
        bool debug= false;
        while(interval < size)
        {
            for(int i=0; i<size-interval; i*=2)
            {

                lists[i] = mergeTwoLists(lists[i], lists[i+interval], debug=debug);
                if (i==0)
                    i++;
            }
            interval*=2;
        }

        if (size)
            return lists[0];
        else
        {
            ListNode* ret=NULL;
            return ret;
        }

    }


};

由于某种原因，此输入[-10，-9，-9，-3，-1，-1,0，-5,4，-8，[]，-9，-6，-5，-4，-4，-2,2,3，-3，-3，-2，-1,0]引发了无限循环。

我在排序2列表算法的第二个列表参数中得到了一个无限循环。我相信它发生在代码行中的一些迭代中：

                curr->next = l2;  
                l2 = l2->next;

有人能给我点提示吗？

Answer 1

看起来你的mergeTwoLists修改了传递给它的两个列表，这样它们就可以共享节点了。这不会是一个问题(至少不是一个大问题)，如果你确定把它们中的一个放在一边，并且永远不再使用它。

显然，这正是您希望在mergeKLists中进行索引调整的原因，但是有一个bug:您错误地增加了i。您重用了一个不应该使用的列表，在共享一个节点的两个列表上调用mergeTwoLists，它会在列表中创建一个循环并永远迭代。

快速解决方案是修复mergeKLists中的索引算法。更深层次的解决方案是更加小心地使用mergeTwoLists中的指针，这样两个不相交的列表就会不相交。