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.