这是合并两个排序列表的问题。我可以理解问题出在哪里?

问题描述 投票:1回答:2

程序接受两个排序的链表,并通过合并这些链表返回一个链表。我也写了考虑边缘情况的逻辑,但是输出没有到来。我认为问题在于第三个链表的形成。我无法形成第三个链接列表。

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *l3 = new ListNode(0);
        ListNode *head = l3;
        ListNode *temp = new ListNode();
        if (!l1 && !l2) {
            return l1;
        } else if (!l1) {
            return l2;
        } else if (!l2) {
            return l1;
        } else if (l1->val <= l2->val) {
            l3->val = l1->val;
            l1 = l1->next;
        } else {
            l3->val = l2->val;
            l2 = l2->next;
        }
        while (l1->next || l2->next) {
            print(head);
            print(l1);
            print(l2);
            if (l1->val <= l2->val) {
                temp->val = l1->val;
                l1 = l1->next;
            } else {
                temp->val = l2->val;
                l2 = l2->next;
           }
            print(temp);
            //l3 = l3->next;
            l3->next = temp;
            l3 = l3->next;
        }
        return head;
    }
};
merge linked-list mergesort
2个回答
1
投票

您的核心问题在于,您没有为新列表中的每个项目分配新节点:

您从l3开始,它是代表合并列表开始的新ListNode,并将l3->val设置为适当的起始值(l1->vall2->val的最小值)。稍后,您将执行与temp类似的操作,评估列表的“当前”节点(现在由l1和l2指向),并将temp->val设置为两者中的最小值。 问题出在,因为l1,l2,l3和temp都是ListNodes的pointers。您反复设置l3-> next以指向同一块内存(由temp指向),并且在每次循环迭代时都覆盖基础值成员。我的建议是将temp的工作视为“移交”它指向的ListNode(成为l3->next)并更改为指向新的内存以容纳新的ListNode(用于下一次迭代),或者更好通过从l1或l2中提取min value并执行简单的l3->next = new ListNode(min_val)来完全消除温度。使用l1,l2和l3确切地指向单独的内存块,可能会有助于绘制一个内存图,这样您就可以移动箭头并捕获更多边缘情况。

其他一些可能会使您绊倒的事情:

1)考虑您的循环条件-您已设置(循环之前和循环中的)l1 = l1->nextl2 = l2->next,然后继续在循环条件中引用该new值的next成员而不检查新值本身是否为null。当您到达一个列表的末尾,但没有另一个列表的末尾时,此陷阱(空取消引用)也可能影响检查val成员。

2]起始l3->val为0,通常不建议使用任意数字。这将是整合的好时机,在检查l1和l2都不为空之后,类似ListNode* l3 = new ListNode(min(l1->val, l2->val))

3)您的第一个条件没有用,因为(如果我假设如果两个列表都为空,则正确地返回null)一个列表为null只是意味着返回另一个列表是正确的,无论如何通过以下两个条件发生。

我希望有帮助!


0
投票

如果目标是合并列表,则不应分配新节点,而只需更改next成员以形成单个有序列表即可。有2个阶段:

  • 只要两个列表中都有节点,则比较头节点以确定从哪个列表中获取第一个元素并将其链接到合并列表。
  • 其中一个列表用尽时,将另一个列表链接到合并列表的末尾。

要在合并列表的末尾链接元素,请保留指向最后一个节点的指针。

这里是修改后的版本:

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *l3 = NULL;
        ListNode *head = NULL;
        ListNode *n;
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                n = l1;
                l1 = l1->next;
            } else {
                n = l2;
                l2 = l2->next;
            }
            if (l3) {
                l3 = l3->next = n;
            } else {
                l3 = head = n;
            }
        }
        if (l1) {
            n = l1;
        } else {
            n = l2;
        }
        if (l3) {
            l3->next = n;
        } else {
            head = n;
        }
        return head;
    }
};

一旦掌握了双指针,就可以改进此代码并删除头节点的测试:

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *head = NULL;
        ListNode **nextp = &head;
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                *nextp = l1;
                nextp = &l1->next;
                l1 = l1->next;
            } else {
                *nextp = l2;
                nextp = &l2->next;
                l2 = l2->next;
            }
        }
        *nextp = l1 ? l1 : l2;
        return head;
    }
};
© www.soinside.com 2019 - 2024. All rights reserved.