C#链表克隆代码合理性校验及简易实现方法咨询

这段代码不属于合理的链表克隆实现，存在明确的功能bug和设计缺陷：

• 循环边界错误：循环终止条件写为i <= count，当链表有效节点数为count时，该逻辑会多执行1次遍历。当tmp移动到尾节点的next（即null）时，再访问tmp.data会直接抛出空引用异常。
• 缺失边界判空：如果原链表是空链表（head为null），循环第一次迭代就会访问空对象的data属性，直接报错。
• 不支持复杂链表克隆：如果你的链表是带random随机指针的复杂链表，该实现仅复制了节点的data值和next指向顺序，完全没有处理random指针的映射关系，克隆出的链表随机指针仍指向原链表节点，不属于完整深拷贝。
• 编码规范问题：C#公共类型、方法名需遵循帕斯卡命名规则，linkedList、clone()的命名不符合常规C#编码规范。

根据链表结构的不同，有几种实现简单、不容易出bug的方案：

普通单链表（仅含next指针）：无计数遍历法 #

完全抛弃依赖count变量的for循环逻辑，用节点本身的空值判断作为遍历终止条件，从根源上避免边界计数错误，实现逻辑：

1. 初始化新链表对象，先判断原链表头节点是否为null，是则直接返回空链表
2. 用临时变量从原链表头节点开始遍历，只要临时变量不为null，就把当前节点的data追加到新链表，再把临时变量移动到下一个节点
   参考实现代码：

public LinkedList Clone()
{
    LinkedList newList = new LinkedList();
    // 空链表直接返回
    if (head == null) return newList;
    Node tmp = head;
    // 不用计数，走到null就停，不会越界
    while (tmp != null)
    {
        newList.Add(tmp.data);
        tmp = tmp.next;
    }
    return newList;
}

带随机指针的复杂链表：字典映射法 #

逻辑直白不容易写错，适合新手实现，仅需额外O(n)的哈希表空间：

• 第一遍遍历原链表，为每个原节点创建一个值相同的克隆节点，存入字典：key为原节点对象，value为对应的克隆节点，这一步暂不设置next和random指针
• 第二遍遍历原链表，从字典中取出当前节点对应的克隆节点，将克隆节点的next指向原节点next对应的克隆值、random指向原节点random对应的克隆值即可
• 最终返回头节点对应的克隆节点就是完整的克隆链表。

带随机指针的复杂链表：原地拆分法 #

不需要额外哈希表空间（除返回的新链表外空间复杂度O(1)），逻辑分三步也很好记：

• 第一轮遍历原链表，在每个原节点的后面插入一个值相同的克隆节点，比如原链表结构A->B->C会变成A->A'->B->B'->C->C'
• 第二轮遍历修改后的链表，给克隆节点设置random指针：如果原节点的random指向节点X，那么原节点后面跟着的克隆节点的random，就指向X后面跟着的X的克隆节点
• 第三轮遍历把拼接在一起的原链表和克隆链表拆开，原节点重新连回原来的后继节点，克隆节点连到对应的下一个克隆节点，拆分完成后就得到独立的克隆链表。

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