Reverse a Linked List

Problem Statement

Given the head of a singly linked list, reverse the list and return the new head.

---

Example

Input
1 -> 2 -> 3 -> 4 -> 5

Output
5 -> 4 -> 3 -> 2 -> 1

---

Approach 1 Iterative Method

Reverse the links of the list one by one.

---

Steps

1 Initialize three pointers previous as None, current as head, next as None
2 Traverse the list
3 Store next node
4 Reverse current node link
5 Move previous and current one step forward
6 Repeat until current becomes None

---

Code

```python id="ll1"
class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next

def reverseList(head):
prev = None
curr = head

while curr:
    next_node = curr.next
    curr.next = prev
    prev = curr
    curr = next_node

return prev

---

## Approach 2 Recursive Method

Reverse the list using recursion.

---

### Code



```python id="ll2"
def reverseList(head):
    if not head or not head.next:
        return head

    new_head = reverseList(head.next)

    head.next.next = head
    head.next = None

    return new_head

---

Explanation

In the iterative method, we reverse the direction of pointers step by step.
In the recursive method, we reverse the rest of the list and then fix the current node.

---

Expected Output

Input
1 -> 2 -> 3 -> 4 -> 5

Output
5 -> 4 -> 3 -> 2 -> 1

---

Conclusion

Reversing a linked list is a fundamental problem that helps in understanding pointers and data structures. It is frequently asked in coding interviews.

Practice both iterative and recursive methods to strengthen your understanding.