Reversing a Linked List

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> currentNode = this.head;
	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
	this.head = prevNode;


}

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
		this.head = currentNode;

	} 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: Index of a substring