C++ 链表中的虚拟节点

Question

我正在尝试开发一种解决链表问题的方法，而不必以任何特殊方式关心头节点，即在链表问题中，我们通常在开始之前单独处理头指针下一个节点。

我找到了一个方法：使用虚拟节点，使实际链表从dummy.next开始。

我正在尝试用这种方式解决 problem:

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

 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        ListNode dummy = ListNode(0);
        ListNode * temp = dummy.next;
        int carry =0;

        while(l1!=NULL && l2!=NULL)
        {
            int x = (l1->val + l2->val + carry)%10;
            temp = new ListNode(x);
            carry = (l1->val + l2->val + carry)/10;
            temp = temp->next;
            l1 = l1->next;
            l2 = l2->next;
        }

        ListNode * p = (l1!=NULL)?l1:l2;

        while(p!=NULL)
        {
            int x = (p->val+carry)%10;
            temp = new ListNode(x);
            carry = (p->val+carry)/10;
            temp = temp->next;
            p = p->next;
        }

        if(carry==1) temp = new ListNode(1);

        return dummy.next;

    }

int main()
{
    ListNode * l1 = new ListNode(0), *l2 = new ListNode(0);
    ListNode * l3 = addTwoNumbers(l1,l2);

}

在这个问题中我尝试不单独初始化一个头节点。显然，代码没有按照我的意愿执行，但我尝试过这种方式，现在我无法弄清楚如何继续使用这种方法。

即使用dummy节点，这样就不需要单独处理新建链表的头节点了。

有什么方法可以使用这种方法来解决问题吗？

Answer 1

有或没有虚拟节点，构建新列表的一个关键部分是在您的逻辑位置后面保留一个节点。我更喜欢在没有虚拟节点的情况下这样做，因此用于当前位置的指针是 ListNode** temp 并且您使用 (*temp)=new ListNode(x) 分配新节点并使用 temp=&(*temp)->next 前进到下一个（前任）位置。如果您更喜欢使用虚拟节点，您可以使用 ListNode* temp=&dummy; 并使用 temp->next=new ListNode(x) 分配新节点，并且只有在您的逻辑位置超出该位置后才使用 temp=temp->next 前进。

根据您的评论进行编辑。如果你想避免双指针的语法（不是现实）：

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        ListNode dummy = ListNode(0);
        ListNode * temp = &dummy;
        int carry =0;

        while(l1!=NULL || l2!=NULL)
        {
            if (l1!=NULL)
            {
                 carry += l1->val;
                 l1 = l1->next;
            }
            if (l2!=NULL)
            {
                 carry += l2->val;
                 l2 = l2->next;
            }

            temp = temp->next = new ListNode(carry%10);
            carry /= 10;
        }

        if(carry==1) temp->next = new ListNode(1);

        return dummy.next;

    }

Answer 2

这些部分是你的问题：

        temp = new ListNode(x);
        carry = (l1->val + l2->val + carry)/10;
        temp = temp->next;

您创建一个新的 ListNode，然后使用 temp = temp->next 忘记它。当时 temp->next 是 NULL，您将失去访问之前创建的 ListNode 的任何能力，更不用说修改它的 next 指针了。

重新开始。这是设计使然。

Answer 3

遵循这个方法

ListNode * addTwoLists(ListNode * first, ListNode * second) {
    ListNode * res = NULL, * temp, * prev = NULL;
    int carry = 0, sum;
    while (first != NULL || second != NULL) {
        sum = carry + (first ? first->val : 0) + (second ? second->val : 0);
        carry = (sum >= 10) ? 1 : 0;
        sum %= 10;
        temp = new ListNode(sum);
        if (res == NULL)
            res = temp;
        else
            prev->next = temp;
        prev = temp;
        if (first) first = first->next;
        if (second) second = second->next;
    }
    if (carry > 0)
        temp->next = new ListNode(carry);
    return res;
}

C++ 链表中的虚拟节点

Dummy Node in Linked List in C++

c++

algorithm

pointers

linked-list