Reversing a Linked List: A Comprehensive Guide with LeetCode Solution in Java

Linked lists are a fundamental data structure in computer science and are commonly used to implement various data storage and manipulation tasks. One common problem associated with linked lists is reversing them. In this comprehensive guide, we will explore the concept of reversing a linked list, provide a step-by-step explanation, and then dive into a Java solution for the “Reverse Linked List” problem on LeetCode.

Table of Contents

1. Introduction to Linked Lists
2. What is a Linked List?
3. Reversing a Linked List: Step by Step
4. Reversing a Linked List in Java
5. LeetCode Problem: Reverse Linked List
6. LeetCode Solution in Java
7. Conclusion

1. Introduction to Linked Lists

Before we dive into reversing a linked list, let’s start by understanding what a linked list is and how it differs from other data structures.

1.1 What is a Linked List?

A linked list is a linear data structure used for organizing and storing a collection of elements called nodes. Each node in a linked list contains two main parts:

• Data: This part stores the actual element or value you want to store.
• Pointer (or reference): This part contains a reference to the next node in the sequence, forming a chain-like structure.

Unlike arrays, linked lists do not require contiguous memory allocation. This means that nodes can be scattered in memory, and they are connected through these pointers, making them more flexible in terms of dynamic memory allocation and insertion/deletion of elements.

There are various types of linked lists, such as singly linked lists, doubly linked lists, and circular linked lists. In this guide, we will focus on singly linked lists.

2. Reversing a Linked List: Step by Step

Reversing a linked list is a common problem that involves changing the direction of the links between nodes. The goal is to transform a list that looks like this:

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

into a reversed version:

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

Here’s a step-by-step explanation of how to reverse a singly linked list:

2.1 Iterative Approach

1. Initialize Pointers: Create three pointers – prev, current, and next. Set prev and current to null initially, and next to the head of the original linked list.
2. Iterate through the List: Use a loop to traverse the linked list. In each iteration:

• Update next to point to the node next to current.
• Update current to point to prev. This effectively reverses the link between current and prev.
• Move prev and current one step forward by updating their references.

1. Termination Condition: Continue this process until next becomes null. This means you have reached the end of the original list, and prev will be pointing to the new head of the reversed list.
2. Final Step: Update the head of the reversed list to prev, and you have successfully reversed the linked list.

2.2 Recursive Approach

Alternatively, you can reverse a linked list using a recursive approach. Here are the steps:

1. Base Case: The base case for recursion is when the current node is null or the next node is null. In this case, simply return the current node.
2. Recursive Call: Recursively call the reverse function on the next node.
3. Reverse Links: After returning from the recursion, reverse the link between the current node and the next node. Set the next node’s next pointer to the current node.
4. Return New Head: Once the recursion unwinds, the original head of the list becomes the new tail of the reversed list. Return this new head.

3. Reversing a Linked List in Java

Now that we understand the theory behind reversing a linked list, let’s implement these approaches in Java.

3.1 Iterative Approach in Java

Here’s a Java code example for reversing a singly linked list using an iterative approach:

class ListNode {
    int val;
    ListNode next;

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

public class LinkedListReversal {

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = null;
        ListNode next = head;

        while (next != null) {
            current = next;
            next = next.next;
            current.next = prev;
            prev = current;
        }

        return prev;
    }

    // Utility function to print the linked list
    public void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        LinkedListReversal reverser = new LinkedListReversal();

        // Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        System.out.println("Original Linked List:");
        reverser.printList(head);

        // Reversing the linked list
        ListNode reversedHead = reverser.reverseList(head);

        System.out.println("Reversed Linked List:");
        reverser.printList(reversedHead);
    }
}

In this code, we define a ListNode class to represent the nodes of the linked list and a LinkedListReversal class that contains the reverseList method to reverse the linked list iteratively. The printList method is a utility function to print the linked list for verification.

3.2 Recursive Approach in Java

Now, let’s implement the recursive approach to reverse a linked list in Java:

class ListNode {
    int val;
    ListNode next;

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

public class LinkedListReversal {

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode reversedHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return reversedHead;
    }

    // Utility function to print the linked list
    public void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        LinkedListReversal reverser = new LinkedListReversal();

        // Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);


        head.next.next.next.next = new ListNode(5);

        System.out.println("Original Linked List:");
        reverser.printList(head);

        // Reversing the linked list
        ListNode reversedHead = reverser.reverseList(head);

        System.out.println("Reversed Linked List:");
        reverser.printList(reversedHead);
    }
}

In this code, the reverseList method recursively reverses the linked list by calling itself on the next node and then updating the pointers to reverse the links between nodes. The base case checks if the current node is null or the next node is null, indicating the end of the list.

4. LeetCode Problem: Reverse Linked List

Now that we’ve covered the basics of reversing a linked list, let’s explore a LeetCode problem related to this topic.

4.1 Problem Description

Title: Reverse Linked List

Problem Statement:
Reverse a singly linked list.

Example:

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

5. LeetCode Solution in Java

To solve the “Reverse Linked List” problem on LeetCode, you can use the iterative approach that we discussed earlier. Here’s a Java solution for this problem:

class ListNode {
    int val;
    ListNode next;

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

public class ReverseLinkedList {

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = null;
        ListNode next = head;

        while (next != null) {
            current = next;
            next = next.next;
            current.next = prev;
            prev = current;
        }

        return prev;
    }

    public static void main(String[] args) {
        ReverseLinkedList solution = new ReverseLinkedList();

        // Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        System.out.println("Original Linked List:");
        solution.printList(head);

        // Reversing the linked list
        ListNode reversedHead = solution.reverseList(head);

        System.out.println("Reversed Linked List:");
        solution.printList(reversedHead);
    }

    // Utility function to print the linked list
    public void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

In this LeetCode solution, the reverseList method is the same as the one we discussed earlier for reversing a linked list iteratively. The printList method is used to print the linked list for verification purposes.

6. Conclusion

Reversing a linked list is a fundamental problem in computer science and is often encountered in coding interviews and competitive programming. In this guide, we explored the concept of linked lists, learned how to reverse a linked list step by step using both iterative and recursive approaches, and provided Java code examples for both methods.

Additionally, we solved the “Reverse Linked List” problem on LeetCode using the iterative approach and demonstrated how to apply the same principles to solve real coding challenges. Understanding linked lists and mastering the art of reversing them is a valuable skill for any programmer, as it provides insights into fundamental data structures and algorithmic thinking.

Thank You!

Read More –

Symmetric Tree LeetCode | Symmetric Tree LeetCode Solution in Java | Code with Kamlesh – https://kamleshsingad.com/symmetric-tree-leetcode-solution-in-java/

Invert binary Tree | Invert Binary Tree or Mirror Tree LeetCode Solution in Java | Code with Kamlesh – https://kamleshsingad.com/invert-binary-tree-or-mirror-tree-leetcode-solution-in-java/

Merge Two Binary Trees – Leetcode-617 | Merge Two Binary Trees LeetCode Solution in Java – https://kamleshsingad.com/how-to-merge-two-binary-trees-solution-in-java/