Question: Reverse any given Linked List.

Related Tags:

## 1) Iterative method

In the iterative method, we need three `Node` pointers - one pointing to previous, one for the current and one for the next pointer. This approach iterates through the list and rearranges the next pointers node one at a time.

### Complexity

Time: O(n) Space: O(1)

The `nextNode` will always be one ahead the current node.

We change the `currentNode`'s `next` pointer to the previous node. Then we push the previous and current nodes to one node forward.

At the end, we assign the last node as the head of our list.

``````public void reverseIterative() {

Node<E> prevNode = null;
Node<E> nextNode;

while(currentNode != null) {
nextNode = currentNode.getNext();
currentNode.setNext(prevNode);

// Increment prev and current nodes to next nodes
prevNode = currentNode;
currentNode	= nextNode;
}
// Set the head to the front

}
``````

## 2) Recursive method

Just as in any recursive approach, we first need to define the base case. In our base case, the end of the linked list will be reached. In this case, we set the head of the linked list to this tail node (which is now our head).

As we cascade back per each node instance, we assign each node ahead to point to the `currentNode`.

Finally, we also need to set the `currentNode`'s next values to `null`. This is so that once we reach our new tail, we can assign it `null`, completing our reversal.

``````public void reverseRecursive(Node<E> currentNode) {

// base case - we reach the tail (end)
if (currentNode.getNext() == null ) {
// set the head to tail

} else {

reverseRecursive(currentNode.getNext());
currentNode.getNext().setNext(currentNode);

// For when we reach the last node (our new tail) we want to set it to null
currentNode.setNext(null);
}
}
``````

Came up with a better solution or have a question? Comment below!

Next Challenge: