Space 浅拷贝与深拷贝的复杂性

Question

考虑在保持顺序的情况下合并两个排序链表的问题。例如如果

L1: 1->1->2->4

和

L2: 2->3->5

那么结果应该是1->1->2->2->3->4->5。在 Elements of Programming Interview 中，作者在 Java 中提出了以下解决方案，其中包括运行通过两个列表并选择最小值添加到虚拟头：

public static ListNode <Integer> mergeTwoSortedList s (ListNode <Integer> LI,
ListNode <Integer> L2) {  // Creates a placeholder for the result.
   ListNode <Integer> dummyHead = new ListNode<>(® , null);
   ListNode <Integer> current = dummyHead;
   ListNode <Integer> p1 = L1 , p2 = L2 ;
   while (p1 != null && p2 != null) {
        if (p1.data <= p2.data) {
           current.next = p1;
           p1 = p1.next ;
        } else {
           current.next = p2 ;
           p2 = p2.next ;
        }
        current = current.next ;
        }
    // Appends the remaining nodes of p1 or p2.
        current.next = p1 != null ? p1 : p2 ;
        return dummy head.next ; 
}

作者随后指出此解决方案在 space 中的复杂度为 O(1)，因为它没有创建任何额外的节点。

我在 Python 中实现了一个非常相似的解决方案，但我注意到存在以下问题（同样适用于 p2）：

current.next = p1
p1 = p1.next

我注意到，在 Python 中，在这种情况下，解决方案将无法更新第二行中 p1 的值，同时也会更改该行中 current.next 的值上面（即第一行是浅拷贝），从而使结果列表为 None （相当于空指针）。通过将第一行替换为

可以在 python 中得到一个可行的解决方案

current.next = NewNode(p1.val,None)

其中 NewNode 创建一个新节点，其值与 p1 相同，下一个“指针”指向 None。但是，这显然将利用 O(m+n) space，其中 m 和 n 是两个列表的长度。

但这让我质疑 Java 代码中 if 块内的整个语句。当我执行 current.next = p1 时，我不是在创建列表的（深）副本并因此使用额外的 space 吗？为什么在这种情况下 space 复杂度是 O(1)？我从更算法的角度理解 O(1) space 声明的来源，但我没有在代码中看到这一点。如果 p1 = p1.next 没有更新 current 的值，那么它们之间肯定存在差异，因此一定会发生深拷贝，但这将意味着额外的 space。我错过了什么？

Answer 1

我不知道你在 python 实现中哪里误入歧途了，但如果没有你所做的 current.next = NewNode(p1.val,None) 更改创建额外的节点（因此使用额外的 space).没有执行也没有必要执行深度复制，因为该算法本质上只是操纵指针。也就是说，我认为您缺少的主要内容是对象是 Java 和 Python 中的隐式引用（它们是隐式指针）。这意味着 current 和 p1 只是对节点的两个不同引用（它们本身不是节点）。

关于有问题的代码块：

current.next = p1
p1 = p1.next

当您执行 current.next = p1 时，您将 current 的下一个字段设置为 p1 的值。因为p1是一个节点，即一个对象，而对象是引用，所以p1的值是一个节点的引用。因此，在第一个语句执行后，current.next 是对 p1 所指的相同节点的引用（没有深层复制）。

然后，使用 p1 = p1.next，您重新定义变量 p1，它当前是对节点的引用，是 p1.next 的值：要么引用另一个节点或 None。第二个语句不会更改 p1 引用的基础节点，也不会影响 current.next 的值：您只是让 p1 引用了一个与它之前不同的节点以前。

因为该算法只是通过引用 L1 和 L2 中当前存在的节点来更新下一个字段，而不是创建新节点，所以它是 O(1)。您可以在下面看到一个有效的 python 实现：

class ListNode:
    def __init__(self, data, next):
        self.data = data
        self.next = next

    def print(self):
        def _print(node, seq):
            seq.append(node.data)
            _print(node.next, seq) if node.next else print(seq)
        _print(self, [])


def mergeLists(L1, L2):
    dummyHead = ListNode(None, None)
    current = dummyHead
    p1, p2 = L1, L2
    while p1 and p2:
        if p1.data <= p2.data:
            current.next = p1
            p1 = p1.next
        else:
            current.next = p2
            p2 = p2.next
        current = current.next
    current.next = p1 if p1 else p2
    return dummyHead.next


L1 = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, None)))))
L1.print()  # [1, 2, 3, 4, 5]

L2 = ListNode(3, ListNode(4, ListNode(6, None)))
L2.print()  # [3, 4, 6]

merged = mergeLists(L1, L2)
merged.print()  # [1, 2, 3, 3, 4, 4, 5, 6]

Space 浅拷贝与深拷贝的复杂性

Space complexity in shallow vs deep copy

python

java

complexity-theory

linked-list

space-complexity