时间戳

首页 > 解决方案 > 合并 K 排序的链表中的循环

c++ - 合并 K 排序的链表中的循环

问题描述

我的合并 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,-2,2,3],[-3,-3,-2,-1,0]] 引发无限循环。

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

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

有人可以给我任何提示吗？

标签： c++sortingpointersmerge

解决方案

您似乎mergeTwoLists修改了传递给它的两个列表，以便它们可以从它共享节点中出来。如果您确保将其中一个放在一边并且不再使用它，这不会是一个问题（至少不是一个大问题）。

显然，这就是你想要的 index-juggling in mergeKLists，但有一个错误：你i不正确地增加。你重用一个你不应该使用的列表，调用mergeTwoLists两个共享一个节点的列表，它会在列表中创建一个循环并永远迭代。

快速而肮脏的解决方案是将索引算法固定在mergeKLists. 更深层次的解决方案是对 in 的指针更加小心，mergeTwoLists这样两个不相交的列表就会不相交。

推荐阅读