两个单链表,大小为m,r,想在第二个链表头后插入第一个链表节点,时间复杂度为O(1)方法。
这对我来说真是一个有趣的难题。每次想办法,时间复杂度是O(m+r)
我需要一些提示来解决这个问题。我在这个问题上付出了无用的努力。
编辑:
让我分享一下我目前的情况:
- 创建一个新的链表
- 添加第二个列表的头部
- 仍然是 O(1)
- 添加第一个列表的所有节点
- 变成 (n)
添加第一个列表中的其余节点
成为另一个(n-1)
更新:
你怎么看这件事?我在这里问完后直接受到启发:)
最佳答案
如果您有两个单向链表并且还没有第一个链表的尾部,则这仅在 O(n) 中是可能的。如果你有尾部,你只需让它指向第二个列表的头部......
编辑:第二个列表头指向第一个列表的头。持有对第二个列表的第二个节点的引用。迭代第一个列表 - 如果您没有开始的尾部引用,这也是 O(n) - 并使该尾部指向第二个列表的原始第二个元素。
关于java - 在 O(1) 中将链表添加到另一个链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12901862/