比较 space 两种反向链表算法的复杂度

Question

public static Node reverseLinkedList1(Node head) {
    if(head == null) return null;
    Node node = null;
    while(head != null) {
      Node newNode = new Node(head.data);
      newNode.next = node;
      node = newNode;
      head = head.next;
    } 
    return node;       
  }

  public static Node reverseLinkedList2(Node head) {
    if(head == null) return null;
    Node node = null;
    while(head != null) {
      Node next = head.next;
      head.next = node;
      node = head;
      head = next;
    }
    return node;
  }

这两个算法是否相同 SPACE 复杂度？我知道第二个是 O(1) space 复杂度，第一个呢？ O(N) 或 O(1)?

Answer 1

在第一种情况下，您正在创建 N 个新对象，因此您正在使用 space O(N)。在该方法的末尾，原始列表是 still holding 传递时的引用。您应该将这些引用设置为空，以便 JVM garbage collection 可以使用它们。

我添加了一个单独的 temp 变量来保存当前 head，一旦我们提取 head.next，我们就可以设置 head.next=null。因为现在这些对象没有被任何人引用，将有资格进行垃圾收集。

public static Node reverseLinkedList1(Node head) {
  if(head == null) return null;
  Node node = null;
  Node temp;
  while(head != null) {
    Node newNode = new Node(head.data);
    newNode.next = node;
    node = newNode;
    temp = head;
    head = head.next;
    temp.next = null;
  }
  return node;
}

Answer 2

第一个算法的复杂度为 O(N) space，因为你正在构建一个新的 LinkedList。

让我们通过示例列表看一下算法

Node1 -> Node2 -> Node3 -> null

第一次进入while循环时，会用Node1的数据创建一个新的节点Node1*，对原来的LinkedList没有任何修改。您只是打乱了一些局部变量，导致

Node1 -> Node2 (head) -> Node3 -> null
node = Node1* -> `null`

在第二个 while 循环之后。请注意，Node1 仍在原始列表中。

Node1 -> Node2 -> Node3 (head) -> null
node = Node2* -> Node1* -> null

第三次后

Node1 -> Node2 -> Node3 -> null (head)
node = Node3* -> Node2* -> Node1* -> null

此时，您有两个相同大小的列表。

当然，我只看了Node个实例的数量。由于您在节点之间共享数据，因此实际开销并没有那么大。

第一种算法的好处当然是您的原始 LinkedList 仍然完好无损，而您的第二种算法则不然。

比较 space 两种反向链表算法的复杂度

compare space complexity within two reverse linkedList algorithm

java

algorithm

reverse

linked-list

space-complexity