复制C# LinkedList时同步LinkedListNode指针？求O(n)以下方案

现有方法接收LinkedList<T>和LinkedListNode<T>参数，以current节点作为锚点执行操作，但复制链表后直接使用原节点在复制链表上操作会抛出异常：

System.InvalidOperationException: 'The LinkedList node does not belong to current LinkedList.'

已知通过copy.Find(current.Value)能找到复制链表中对应的节点，但该方法时间复杂度为O(n)，希望找到更低复杂度的实现方案。实际场景为：需对带current指针的链表执行破坏性操作，后续可能需要回滚状态（包括current指针的位置），当前考虑通过记录操作并反向执行来实现回滚。

1. 复制链表时同步建立节点映射（O(n)复制时间，后续操作O(1)） #

复制链表的同时，用字典记录原节点到复制节点的映射关系，后续可直接通过原current节点快速获取复制链表中的对应节点，避免重复遍历：

public static void Foo<T>(LinkedList<T> list, LinkedListNode<T> current)
{
    var nodeMap = new Dictionary<LinkedListNode<T>, LinkedListNode<T>>();
    var copy = new LinkedList<T>();
    
    // 遍历原链表，复制节点并建立映射
    var originalNode = list.First;
    while (originalNode != null)
    {
        var copiedNode = copy.AddLast(originalNode.Value);
        nodeMap.Add(originalNode, copiedNode);
        originalNode = originalNode.Next;
    }
    
    // 直接通过映射获取复制链表中的对应节点
    var copyCurrent = nodeMap[current];
    copy.Remove(copyCurrent);
    // 其他操作如copy.AddAfter(copyCurrent, ...)可正常执行
}

该方案复制链表的时间复杂度仍为O(n)，但后续查找对应节点为O(1)，远优于多次调用Find的重复O(n)遍历，尤其适合需要多次操作锚点节点的场景。

2. 基于操作日志的回滚方案（避免复制整个链表） #

既然核心需求是操作回滚，完全可以跳过链表复制环节，改为记录每次破坏性操作的细节，回滚时反向执行操作即可：

• 记录操作类型（删除、插入前、插入后等）
• 记录操作涉及的节点上下文（如被删节点的前后节点、插入位置的锚点节点等）
• 记录操作前后current指针的位置

示例实现思路：

// 定义操作日志类，存储回滚所需信息
public class LinkedListOperationLog<T>
{
    public enum OperationType { Remove, AddAfter, AddBefore }
    public OperationType Type { get; set; }
    public T NodeValue { get; set; }
    public LinkedListNode<T> AnchorNode { get; set; }
    public LinkedListNode<T> OldPrev { get; set; }
    public LinkedListNode<T> OldNext { get; set; }
    public LinkedListNode<T> OldCurrent { get; set; }
}

// 执行操作时记录日志
var operationLogs = new List<LinkedListOperationLog<int>>();
var list = new LinkedList<int>() { 1, 2, 3, 4, 5 };
var current = list.First;

// 模拟删除操作并记录日志
var nodeToRemove = current;
var removeLog = new LinkedListOperationLog<int>
{
    Type = LinkedListOperationLog<int>.OperationType.Remove,
    NodeValue = nodeToRemove.Value,
    OldPrev = nodeToRemove.Previous,
    OldNext = nodeToRemove.Next,
    OldCurrent = current
};
list.Remove(nodeToRemove);
operationLogs.Add(removeLog);

// 回滚操作：反向执行最后一次操作
var lastLog = operationLogs.Last();
if (lastLog.Type == LinkedListOperationLog<int>.OperationType.Remove)
{
    LinkedListNode<int> restoredNode;
    if (lastLog.OldPrev == null)
        restoredNode = list.AddFirst(lastLog.NodeValue);
    else if (lastLog.OldNext == null)
        restoredNode = list.AddLast(lastLog.NodeValue);
    else
        restoredNode = list.AddAfter(lastLog.OldPrev, lastLog.NodeValue);
    // 恢复current指针位置
    current = lastLog.OldCurrent;
}

该方案无需复制整个链表，空间复杂度取决于操作次数，回滚单步操作的时间复杂度为O(1)，在操作次数远少于链表节点数的场景下，效率远高于复制链表的方案。

关键说明 #

LinkedListNode<T>内部持有对所属LinkedList<T>实例的引用，复制链表仅会复制节点的值，原节点与复制节点分属不同链表实例，因此直接使用原节点在复制链表上操作必然触发异常，必须获取复制链表内对应的节点实例。

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