compare space complexity within two reverse linkedList algorithm

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

Are these two algorithm same SPACE COMPLEXITY? I know the second one is O(1) space complexity, What about the first one? O(N) or O(1)?

Answer 1

The first algorithm has O(N) as space complexity, because you are building a new LinkedList.

Let's take a look at the algorithm with an example list

Node1 -> Node2 -> Node3 -> null

When you enter the while loop for the first time, you will create a new Node Node1* with the data of Node1 and nothing has been modified to the original LinkedList. You just shuffled some local variables, resulting in

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

After the second while loop. Note that Node1 is still in the original list.

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

After the third time

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

At this point, you have two lists of the same size.

Of course, I have only looked at the number of Node instances. Since you share the data between the nodes, the actual overhead is not that big.

The benefit of the first algorithm is of course that your original LinkedList is still intact, which isn't the case for your second algorithm.