Why do I need to make 'head' equal to 'prev' to finish reversing a Linked List?

user_17592667 0
Viewed 55

sorry for the awkward question title. I don't really know how to explain without a code example. I have implemented a Linked List using generics, and I am trying to reverse it.

public Node<T> reverse() {
Node<T> prev = null;

while (head != null) {
  Node<T> next = head.next;
  head.next = prev;
  prev = head;
  head = next;
  System.out.println("head: " + head.next + "\nprev: " + prev.next);
}
head = prev;
return prev;
}

head = prev;

My question is, why is this required?

My LinkedList outputs: [output]

But without the head = prev; line it simply outputs blank []. Is this something to do with generics?

data-structures linked-list
2 Answers

No, It has nothing to do with generics, Looking at your reverse method, initially, there are three nodes prev pointing to null, head pointing to start of the linked list, and next pointing to head's next node. At each step you are moving each node in forward direction until it is reversed, so after completion, your prev node will point to the tail of the linked list which is in fact the start of the reversed linked list, and both head and next pointing to null. So head = prev is needed to make the head point to the starting node of the reversed linked list.

user_92769960

*TLDR; Because at end of while loop, 'head' points to null, not the reversed list.

--

Let’s understand your code by an example: List: 3 -> 6 -> 9 -> null head points to 3. // 1

Node<T> prev = null;
while(head != null) // true
Node<T> next = head.next; // next -> 6, as head.next points to Node with element 6
head.next = prev; // head->next = null, earlier it pointed to Node with element 6, prev is null
prev = head; 
head = next;

Current state:

null <- 3 6 -> 9 -> null
Now, prev points to 3, head points to 6.
// 2
while(head != null) // true
Node<T> next = head.next; // next -> 9, as head.next points to Node with element 9
head.next = prev; // head->next =3, earlier it pointed to Node with element 9, prev is 3
prev = head; 
head = next;

Current state:

null <- 3 <- 6 9 -> null
Now, prev points to 6, head points to 9.    

// 3
while(head != null) // true
    Node<T> next = head.next; // next -> null, as head.next points to null
    head.next = prev; // head->next =6, earlier it pointed to null, prev is 6
    prev = head; 
    head = next;

Current state:

null <- 3 <- 6 <- 9
Now, prev points to 9, head points to null.

// 4
while(head != null) // false

Now, head points to null and you need to return reversed linked list.
head = prev; // prev points to the node with element 9.
// null <- 3 <- 6 <- 9 <- prev (or head) as head and prev are equal.
return prev; // will return the reversed linked list.
return head; // will return the reversed linked list as both prev and head are equal.
user_82588010
Related