将doubly linked list元素高效复制到singly linked list的方法

存在远优于当前O(n²)复杂度的实现方案，甚至可以完全省去复制链表的额外开销，具体方案如下： #

方案1：优化链表复制逻辑，将复制复杂度降到O(n) #

你当前复制操作达到O(n²)的核心原因是：每次往单向链表尾部追加元素时，都需要从头部遍历到尾部找尾节点，单次插入复杂度随已插入元素数量递增，累加后总复杂度为O(n²)。
优化方式非常简单：

• 复制过程中额外维护一个指向单向链表当前尾节点的指针，每次追加新元素时直接操作尾节点插入，单次插入复杂度为O(1)
• 仅需遍历一次你的自定义双向链表，遍历过程中依次将元素插入单向链表尾部即可，总时间复杂度为O(n)
  如果你用的是语言标准库提供的单向链表实现（比如Java的LinkedList、Python的collections.deque），标准库的尾插方法本身已经做了尾指针优化，直接遍历双向链表逐个调用尾插方法即可，不需要自己额外维护尾指针。

方案2：直接让自定义双向链表支持增强for循环，完全省去复制开销 #

这是更推荐的方案，不需要额外开辟链表存储空间，遍历时间复杂度同样为O(n)，比复制方案更优。
增强for循环的底层依赖Iterable接口实现，你只需要给你的双向链表类做对应适配即可，以Java为例：

• 给双向链表类添加implements Iterable<T>声明
• 重写iterator()方法，返回自定义的迭代器实例：
  • 迭代器内部维护当前遍历的节点指针，初始化时指向双向链表的头节点
  • hasNext()方法判断当前指针是否非空，返回是否还有下一个元素
  • next()方法返回当前节点存储的元素值，同时将指针后移一位
    适配完成后，你可以直接对自定义双向链表使用增强for循环打印元素，不需要任何中间复制操作。

注：如果需要规避遍历时链表结构被修改导致的异常，可以增加修改计数校验逻辑：链表类维护修改次数字段，每次增删节点时计数+1；迭代器初始化时记录当前计数，每次调用next()方法时先校验计数是否变化，如有变化直接抛出ConcurrentModificationException即可。

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