O(1) 中的双向链表切片

Question

以下代码表示切片函数的实现。
假设 l1 l2 是类 Node(属性id， next， prev( 的对象。

我想返回 l1 和 l2

之间的元素(包括 l1 和l2(，然后显然更改上一个和下一个值，因为这个切片将不再存在：

def splice(self, l1, l2):
        curr = l1
        s = ""
        while curr.next:
            s += str(curr) + "n"
            if curr is l2:
                break
            curr = curr.next
        if l1.prev is not None:
           l2.prev = l1.prev
        else:
           self.first = l2.next
           self.first.prev = None
        if l2.next is not None:
           l1.next = l2.next
        else:
            self.last = l2.next
        return s

我加倍了这个代码的时间复杂度是 O(1(，我认为它会是 O(n(因为 While-loop。
无论如何，我在 O(1( 中做同样的功能吗？

Answer 1

拆分链表有两个部分：

1. 查找要拆分的节点
2. 拆分列表

不幸的是，1. 将始终是 O(n(。 没有办法像使用数组那样"跳"到链表。

好消息是 2. 是 O(1( 操作。

这是什么意思？

好吧，如果你拿一个列表并想在n个元素之后切片它，那么你需要通过这么多元素进行搜索，然后切片。

但是，如果您已经在列表上执行操作，则您可能具有对要进行剪切的列表元素的引用。 在这种情况下，您无需再次搜索列表。

我在上周编写的一些代码中很好地使用了它。

Answer 2

假设两个参数都已经在链接中，我认为这可以工作。

画

一幅画会更容易理解

[l1.prev]-[l1]-[l1.next]---[l2.prev]-[l2]-[l2.next]

这个想法是你想要

1. 设置l1.prev.next = l2.next以加入从左向右移动的列表
2. 设置l2.next.prev = l1.prev以加入从右向左移动的列表
3. 设置l1.prev = None和l2.next = None以从初始列表中删除l1到l2
4. 返回l1，拼接子列表。

我可能把这些步骤搞砸了，但也许像这样

def splice(self, l1, l2):
   before, next = l1.prev, l2.next
   # self.head = ... # TODO: Figure out what this should point at          
   if l2.next:
       l2.next.prev = before if l1 else None  # right-to-left
   if l1.prev:
       l1.prev.next = next if l2 else None # left-to-right
   if l1:
       l1.prev = None # detach <-l1
   if l2:
       l2.next = None # detach l2->
   return l1  # return the sublist 

请注意，查找 l1 和 l2 都是 O(N( 操作