Reverse a linked list by changing links between nodes

Reverse a linked list by changing links between nodes

Reverse a Linked List is one of the most commonly asked interview questions for data structures. It helps developers understand how pointers or references work in linked lists.

In this article, we will discuss how to reverse a singly linked list by changing links between nodes, using Java. This article covers:

  1. How to reverse a linked list ?
  2. Detailed algorithm explanation
  3. Java code implementation (iterative and recursive)

What Does Reverse a Linked List Mean?

Reversing a linked list means changing the direction of the next pointers so that:

1 -> 2 -> 3 -> 4 -> null

becomes:

4 -> 3 -> 2 -> 1 -> null

We do not create a new list or use any array. Instead, we manipulate the links between existing nodes.

Reverse a linked list by changing links between nodes
Reverse a linked list by changing links between nodes

Approach To Reverse a Linked List

There are two main approaches to reverse a singly linked list:

  1. Iterative Method: using loop and pointer manipulation.
  2. Recursive Method: using function call stack.

Node Structure in Java

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Method 1: Iterative Approach to Reverse a Linked List

Algorithm:

  1. Initialize three pointers:
    • prev as null

    • curr as head

    • next as null (temporary holder)

  2. Loop while curr is not null:

    • Store curr.next in next

    • Change curr.next to point to prev

    • Move prev to curr

    • Move curr to next

  3. Set head = prev (new head)

Code:

Run
public class LinkedListReversal {

    static class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
        }
    }

    // Function to reverse the linked list
    public static Node reverseIterative(Node head) {
        Node prev = null;
        Node curr = head;
        Node next;

        while (curr != null) {
            next = curr.next;      // Step 1: store next
            curr.next = prev;      // Step 2: reverse pointer
            prev = curr;           // Step 3: move prev forward
            curr = next;           // Step 4: move curr forward
        }

        return prev; // New head
    }

    // Function to print list
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.println();
    }

    // Example usage
    public static void main(String[] args) {
        Node head = new Node(10);
        head.next = new Node(20);
        head.next.next = new Node(30);
        head.next.next.next = new Node(40);

        System.out.print("Original List: ");
        printList(head);

        head = reverseIterative(head);

        System.out.print("Reversed List: ");
        printList(head);
    }
}

Input:

Original List: 10 20 30 40

Output:

Reversed List: 40 30 20 10

Method 2: Recursive Approach to Reverse a Linked List

Algorithm:

  1. If head is null or only one node, return it.
  2. Recursively call reverse on head.next.
  3. Change head.next.next to point to head.
  4. Set head.next = null.
  5. Return the new head.

Code:

Run
public class RecursiveReverse {

    static class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
        }
    }

    public static Node reverseRecursive(Node head) {
        // Base condition
        if (head == null || head.next == null)
            return head;

        // Recur for the rest of the list
        Node rest = reverseRecursive(head.next);

        // Change links
        head.next.next = head;
        head.next = null;

        return rest;
    }

    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(3);
        head.next.next = new Node(5);
        head.next.next.next = new Node(7);

        System.out.print("Original List: ");
        printList(head);

        head = reverseRecursive(head);

        System.out.print("Reversed List: ");
        printList(head);
    }
}

Input:

Original List: 1 3 5 7

Output:

Reversed List: 7 5 3 1

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Edge Cases to Consider for Reverse of Linked List

  1. Empty List
    Input: null
    Output: null
  2. Single Node List
    Input: 5
    Output: 5
  3. Already Reversed List
    No harm; reversing twice restores original

Comparison between both methods:

FeatureIterativeRecursive
Time ComplexityO(n)O(n)
Space ComplexityO(1)O(n) due to stack
SimplicityEasy to understandElegant but stack-heavy
Suitable for Large List?YesNo (risk of StackOverflow)

Conclusion

Reversing a linked list by changing the links is a fundamental algorithm that demonstrates a deep understanding of pointer manipulation and memory management.

  1. Using Java, we explored both iterative and recursive approaches to solve the problem.
  2. Iterative method is space-efficient and preferred for large lists.
  3. Recursive method is elegant but uses stack space.

Understanding both methods strengthens your grasp on linked list operations and prepares you for technical interviews and real world problems.

FAQ's related to Reverse a linked list

Answer:

Yes. The iterative method reverses the list in place using O(1) space.

Answer:

Most efficient method to reverse a singly linked list in Java is using the iterative approach, which reverses the links between nodes in-place with a time complexity of O(n) and space complexity of O(1).

Answer:

Yes. By changing the next pointers of each node using an iterative approach, you can reverse a linked list in Java without using any additional data structure or space.

 

Answer:

In recursion, the reversal happens by recursively reaching the end of the list and then modifying the next pointers while the call stack unwinds. This method uses O(n) space due to the call stack and is more elegant but less memory efficient for large lists.

Answer:

Iterative approach is space efficient and faster for large lists, while the recursive method is cleaner but uses extra memory due to recursion.

Iterative reversal is preferred in production level code for large data sets.

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription