合并两个排序链表时的无限循环

Question

我运行遇到链表中的最后一个节点被重复复制的问题。

参数列表 1 = [1,2,4]
参数列表 2 = [1,3,4]
预期结果 = [1,1,2,3,4,4]
实际结果 = [1,1,2,3,4,4,4,4,4,4,...]

在 return 之前的最后一个 else 语句中发生了一些事情，它重复了 4 多次，我无法弄清楚它是什么。是什么导致最终节点的行为像这样？是我的 SinglyLinkedNode 有问题吗Class?

在执行 current.next = list2 之前，值为

当前 = [1,1,2,3,4]
list2 = [4]

执行后的值为

当前 = [1,1,2,3,4,4,4,4,4,..]
list2 = [1,1,2,3,4,4,4,4,4,...]

public static SinglyLinkedNode MergeTwoSortedLists(SinglyLinkedNode list1, SinglyLinkedNode list2)
{
    //if one list is null, return the other
    if (list1 == null) return list2;
    if (list2 == null) return list1;

    //declare the result node; declare the node that you will fill
    SinglyLinkedNode result = new SinglyLinkedNode();
    SinglyLinkedNode current = result;

    //while neither lists are empty
    while (list1 != null && list2 != null)
    {
        //do the comparisons and populate the current Node;
        if (list1.val <= list2.val)
        {
            current.next = list1;
            list1 = list1.next;
        }
        else
        {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }
    //when one list is empty, use the remaining list to fill the current node
    if (list1 != null)
    {
        current.next = list1;
    }
    else
    {
        current.next = list2;
    }
    
    return result.next;
}

public class SinglyLinkedNode
{
    public int val;
    public SinglyLinkedNode next;
    public SinglyLinkedNode(int val = 0, SinglyLinkedNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

Answer 1

我在初始化参数的时候出错了，因为我有一个 list2 节点指向 list1 节点。

Answer 2

首先，必须重要的概念

当您使用以下代码时，请不要克隆对象，而是克隆对象的指针。在第 2 行中，赋值后 current.next 引用 list1.next。

 1- current.next = list1;
 2- list1 = list1.next;

但是您可以像这样更改您的代码。

1- 更新您的对象 public class SinglyLinkedNode : ICloneable 并实施此方法。

public class SinglyLinkedNode : ICloneable
{
    // other code
    public object Clone()
    {
         return new SinglyLinkedNode(val, null);
    }
}

2 - 在此处更改

//when one list is empty, use the remaining list to fill the current node
if (list1 != null)
{
    current.next = list1;
    list1 = list1.next;
}
else
{
    current.next = list2;
    list2 = list2.next;
}

--- 在这里，我们有一个很好的 example

合并两个排序链表时的无限循环

Infinite Loop when merging two sorted Linked List

c#

linked-list

singly-linked-list

首先，必须重要的概念