Reverse A linked List - Recursive & Iterative

Iterative:

1. The head node’s next pointer should be set to NULL since the head will become the tail. This is an exception for the head node, and can be done outside the while loop. But, before we do this we will need a temp variable to point to the 2nd node (the node after the head node), because the only way to reference the 2nd node is through the head node’s next pointer.
2. The 2nd node (the node after the head node) should have it’s own next pointer changed to point to the head node. This will reverse the order of the nodes. But, remember that the 2nd node’s next pointer will at first be pointing to the 3rd node. This means that before we change the 2nd node’s next pointer, we have to save a reference to the 3rd node otherwise we will have no way of referencing the 3rd node. So, we simply store a reference to the 3rd node in a variable before we change the 2nd node’s next pointer.
3. The 3rd node then becomes the “first” node in the while loop and we repeat the process of changing pointers described in step 2.
4. Continue step 3 until we come across a node that has a next pointer set to NULL. When we do come across a NULL next pointer we just set the head node to point to the node that has the NULL next pointer. This node was previously the tail node, but is now the head node because we are reversing the linked list.

public reverseListIteratively(Node head) {
if (head == NULL || head.next == NULL)
return; // empty or just one node in list
Node Second = head.next;
// store third node before we change
Node Third = Second.next;
// Second's next pointer
Second.next = head; // second now points to head
head.next = NULL; // change head pointer to NULL
// only two nodes, which we already reversed
if (Third == NULL)
return;
Node CurrentNode = Third;
Node PreviousNode = Second;
while (CurrentNode != NULL) {
Node NextNode = CurrentNode.next;
CurrentNode.next = PreviousNode;

/*
* repeat the process, but have to reset the PreviousNode and
* CurrentNode
*/
PreviousNode = CurrentNode;
CurrentNode = NextNode;
}

head = PreviousNode; // reset the head node
}

Recursive:

public void recursiveReverse(Node currentNode) {

// check for empty list

if (currentNode == NULL)

return;

/*

* if we are at the TAIL node: recursive base case:

*/

if (currentNode.next == NULL) {

// set HEAD to current TAIL since we are reversing list

head = currentNode;

return; // since this is the base case

}

recursiveReverse(currentNode.next);

currentNode.next.next = currentNode;

currentNode.next = null; // set "old" next pointer to NULL

}