java - 在 O(1) 中将链表添加到另一个链表

Question

两个单链表，大小为m，r，想在第二个链表头后插入第一个链表节点，时间复杂度为O(1)方法。

这对我来说真是一个有趣的难题。每次想办法，时间复杂度是O(m+r)

我需要一些提示来解决这个问题。我在这个问题上付出了无用的努力。

编辑:

让我分享一下我目前的情况:

1. 创建一个新的链表
2. 添加第二个列表的头部
3. 仍然是 O(1)
4. 添加第一个列表的所有节点
5. 变成 (n)

6. 添加第一个列表中的其余节点

7. 成为另一个(n-1)

更新:

你怎么看这件事？我在这里问完后直接受到启发:)

Answer 1

如果您有两个单向链表并且还没有第一个链表的尾部，则这仅在 O(n) 中是可能的。如果你有尾部，你只需让它指向第二个列表的头部......

编辑:第二个列表头指向第一个列表的头。持有对第二个列表的第二个节点的引用。迭代第一个列表 - 如果您没有开始的尾部引用，这也是 O(n) - 并使该尾部指向第二个列表的原始第二个元素。