Reverse a linked list (Recursion, Iterative, Using Stack, Using Array)

In this iterative approach, first we initialize three variables—"current = head", "prev = null" and "next = null".

Next, we iterate over the list with the help of a "while-loop", unitil "current!=null".

In each iteration, do the following:

1) Keep next node safe i.e. next = current.next
2) Point current backwards i.e. current.next=prev
3) Move 'prev' one step forward, i.e., prev=current
4) Move 'current' one step forward, i.e., current=next

The time complexity of this solution is O(n) and space complexity is O(1).

In this approach, we can reverse the linked list with the help of an auxiliary array of length "n".

The idea is to first iterate the linked list to get length (n), and second, initialise an array of length "n".

Next, iterate the linked list for the second time to fill the array with link list nodes.

Now, point "newHead" and a "movingPointer" to the array's last (n-1 th) element. (the last element of the array will act as the new head of the reversed list).

Next, iterate over the array from the "last-1 th" element to "0" and in each iteration do the following:

movingPointer.next = arr[i];
movingPointer = movingPointer.next;

Once the array is exhausted, point "movingPointer.next" to "null". (At this moment, "movingPointer" is pointing to the last element).

The time complexity of this solution is O(n) and space complexity is O(n).

The idea is to keep track of two variables, i.e., "current" and "prev" and also maintain a local variable, "next".

In each recur, keep the next node safe in the local variable "next" and do the following:

1) Point current backwards i.e. current.next=prev
2) Move 'prev' one step forward  i.e. prev=current
3) Move 'current' one step forward  i.e. current=next

Base Condition: If last node is reached i.e. "current.next == null", make current to point to "prev (remaining list)" and return "current (new head)".

The time complexity of this solution is O(n) and space complexity is O(1).

In this approach, we can reverse the linked list with the help of an auxiliary stack of length "n".

The idea is to iterate the linked list and push its elements into a stack. (Because the stack is a LIFO data structure, we can pop the elements in reverse order.)

Now, pop the top element from the stack and point "newHead" and "movingPointer" to it. This "newHead" variable will serve as the "head" of the reversed list, and "movingPointer" will assist us in reversing the pointers.)

Now keep pooping elements until the stack is empty and in each iteration do the following:

movingPointer.next = stack.pop()
movingPointer = movingPointer.next

Once the stack is exhausted, point "movingPointer.next" to "null". (At this moment, "movingPointer" is pointing to the last element).

The time complexity of this solution is O(n) and space complexity is O(n).