传入相同参数两次调用合并链表函数触发死循环的原因是什么

问题原因 #

你遇到的死循环本质是第二次调用合并函数时在链表中构造了循环链，具体触发过程如下：

1. 你的mergeTwoLists函数没有生成新的链表节点，而是直接修改原链表的指针：会直接把入参l2的头节点接在l1的尾节点后面，修改的是原l1的结构。
2. 第一次调用mergeTwoLists(l1,l2)后：
   • 原l1的尾节点next已经指向了l2的头节点，此时l1的完整链为4→2→1→1→3→4→null，链的尾节点就是原l2的尾节点（值为4的节点）
   • 原l2本身的结构没有变化，仍然是1→3→4→null
3. 第二次调用mergeTwoLists(l1,l2)时：
   • 函数遍历当前l1找到尾节点（也就是原l2的尾节点，值为4，此时next为null）
   • 再次把这个尾节点的next赋值为l2.head
   • 此时就形成了循环链：1（l2头）→3→4→1（l2头）→3→4...
   • 遍历输出的show方法碰到循环链就会永远遍历下去，产生你看到的无限重复输出。

如果要避免这个问题，可选择两种修改方案：

• 每次合并时生成新的链表节点，不修改原入参链表的结构
• 合并后将l2置空，或者每次合并前判断l1是否已经接入过l2
• 如果你需要重复合并相同的l2，可以对l2做深拷贝后再接入l1

内容的提问来源于stack exchange，提问作者user17146394