比较两种反向linkedList算法的空间复杂度

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;
  }

这两个算法是相同的空间复杂度吗?我知道第二个是0(1)的空间复杂度，第一个呢?O(N)还是O(1)?

Answer 1

第一个算法的空间复杂度为0 (N)，因为您正在构建一个新的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仍然是完整的，而第二种算法则不是这样。

Answer 2

在第一种情况下，您正在创建N新对象，因此您正在消耗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;
}