Java  

How to Reverse a Linked List in Data Structures with Examples

🧩 What is a Linked List?

A linked list is a linear data structure where elements, called nodes, are connected using pointers. Each node consists of:

  • Data: The value to store.
  • Pointer (next): Reference to the next node.

Unlike arrays, linked lists are not stored in contiguous memory. This makes them flexible for dynamic memory allocation but slower for direct indexing.

Example

[10 | next] → [20 | next] → [30 | null]

Here, null means there’s no further node.

📜 Problem Statement

We want to reverse the sequence of nodes in a linked list. Reversing means changing the direction of the next pointers so that the head becomes the tail and vice versa.

Example

Input:  1 → 2 → 3 → 4 → null
Output: 4 → 3 → 2 → 1 → null

This requires pointer manipulation without losing track of the remaining list.

🐌 Iterative Approach

We traverse the list once, adjusting each node’s next pointer to point to its previous node.

Initialize Pointers

  • prev = null (no previous node initially)
  • current = head (start from the first node)

Loop Until End

  • Save the next node: next = current.next
  • Reverse the link: current.next = prev
  • Move prev forward: prev = current
  • Move current forward: current = next

Update Head: At the end, prev becomes the new head.

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    while (current != null) {
        ListNode next = current.next; // save next node
        current.next = prev; // reverse pointer
        prev = current; // move prev forward
        current = next; // move current forward
    }
    return prev; // new head
}

Complexity

  • Time: O(n) – Each node is visited once.
  • Space: O(1) – No extra storage used.

🔄 Recursive Approach

Reverse the rest of the list first, then adjust the current node’s pointer.

Steps

  1. Base Case: If the head is null or only one node exists, return it.
  2. Recursive Call: Reverse the list starting from head.next.
  3. Rewire Pointers: Set head.next.next = head and head.next = null.
public ListNode reverseListRecursive(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

Complexity

  • Time: O(n) – Each node is visited once.
  • Space: O(n) – Recursive stack memory.

🧠 Importance of Learning This

  • Common in coding interviews.
  • Teaches pointer manipulation.
  • Helps with advanced problems like palindrome-linked lists, list rotations, and merging operations.

Summary

Linked list using two main approaches: iterative and recursive. The iterative method uses pointer updates in a single pass, making it space-efficient. The recursive approach, while elegant, consumes additional stack memory. Understanding linked list reversal strengthens your grasp of pointer manipulation and prepares you for advanced linked list problems commonly seen in coding interviews.

Membership not found