1

两个单向链表，大小为 m ， r 并且想在第二个链表头部之后插入第一个链表节点，该方法的时间复杂度必须为 O(1)。

这对我来说确实是一个有趣的难题。Eatch time我想到一个解决方案，时间复杂度是O(m+r)

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

编辑：

让我分享一下我到目前为止所拥有的：

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

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

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

更新：

你怎么看待这件事？我在这里询问后直接受到启发:) 在此处输入图像描述

4

2 回答 2

4

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

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

于 2012-10-15T18:39:37.697 回答
0

假设你有这些结构：

  • 列表
    • 头节点
    • 尾节点
  • 节点
    • 价值
    • 下一个节点

提醒自己：目标是：“在第二个链表头部之后插入第一个链表节点”。

那么你所要做的就是：

// Hook up the end of list1 to the original second element of list2
list1.tail.next = list2.head.next;
// Set the second element of list2 to be the first element of list1
list2.head.next = list1.head;

List2 仍然在它之前的位置结束（它的尾节点是相同的）。

你现在有了list1一个“浮动”的头，这通常是个坏消息......但是如果你迭代list1你会从两个原始列表中获得所有元素......

于 2012-10-15T19:09:04.137 回答