Describe the process of reversing a linked list iteratively and recursively.

Question

Aryan Kumar · Answer

Sure. Here are the steps on how to reverse a linked list iteratively and recursively:

Iterative Method

Initialize three pointers: prev, curr, and next.
Set prev to None and curr to the head of the linked list.
While curr is not None:
- Set next to curr's next node.
- Set curr's next node to prev.
- Set prev to curr.
- Set curr to next.
The reversed linked list will be from prev to curr.

Recursive Method

Define a recursive function reverse(head) that takes the head of the linked list as input.
If the head is None, then return None.
Otherwise, return the reversed linked list, which is the reversed linked list of the head's next node, with the head node at the end.

Here is an example of the recursive function in Python:

Python

def reverse(head):
    if head is None:
        return None

    prev = None
    curr = head
    next = curr.next

    while curr is not None:
        curr.next = prev
        prev = curr
        curr = next

    return prev

Both the iterative and recursive methods have a time complexity of O(n), where n is the number of nodes in the linked list. This is because both methods need to visit each node in the linked list to reverse it.

The iterative method has a space complexity of O(1), because it only uses three pointers. The recursive method has a space complexity of O(n), because it needs to store the reversed linked list on the stack.

The iterative method is generally more efficient than the recursive method, because it does not need to use the stack. However, the recursive method is easier to understand and implement.

forum

Describe the process of reversing a linked list iteratively and recursively.

Can you answer this question?

1 Answers