Reverse a Linked List

Introduction

Linked Lists are an important data structure where elements are connected using pointers.

One of the most fundamental operations is reversing a linked list, which helps in understanding pointer manipulation.

Problem Statement

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

Example

Input:
1 → 2 → 3 → 4 → 5 → NULL

Output:
5 → 4 → 3 → 2 → 1 → NULL

Intuition

• Reverse the direction of each link
• Instead of pointing forward, each node should point backward

Approach

Algorithm Steps

• Initialize:

  • prev = None
  • curr = head

• Traverse the list:

  • Store next node
  • Reverse current node’s pointer
  • Move prev and curr forward

• Return prev as new head

Code (Python)

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

Step-by-Step Explanation

For 1 → 2 → 3 → 4 → 5:

• Step 1 → 1 → NULL
• Step 2 → 2 → 1
• Step 3 → 3 → 2 → 1
• Continue until full reversal

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Conclusion

Reversing a linked list is a fundamental problem that builds strong understanding of pointer manipulation.