DAY 37: Solved Find Middle, Remove Nth Node from End & Reverse Linked List (Recursive & Iterative) | Linked List

---

🚀 Introduction

Welcome to Day 37 of my DSA Journey!
After wrapping up an intense few weeks focused on Recursion, I’ve recently shifted my focus to one of the most fundamental data structures in DSA — the Linked List.

Transitioning from recursion to linked lists has been a rewarding step, as these concepts are closely connected, especially when tackling problems that involve traversal and pointer manipulation.

Over the past 3 days, I’ve solved several key problems on the Singly Linked List, including: finding the middle of a linked list, removing the Nth node from the end, reversing a linked list using recursion, and reversing a linked list iteratively.

I’m sharing this journey publicly to stay consistent and to help others who are starting their own DSA path from scratch.

Feel free to follow me on Twitter for real-time updates and coding insights!

📅 Here’s What I Covered Over the Last 3 Days:

Day 34

• Find Middle of a Linked List
• Remove Nth Node From End of List

Day 35

• Reverse Linked List – Recursion

Day 36

• Reverse Linked List – Iteration

Let’s dive into each of these topics below 👇

---

Q 1. Find Middle of a Linked List:

Given the head of a singly linked list, you need to return the middle node of the list.
If there are two middle nodes, return the second middle node.

Example:

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

Here, 3 is the middle node as there are two nodes before and two nodes after it.

Input:
1 → 2 → 3 → 4 → 5 → 6
Output:
4

In this case, there are two middle nodes (3 and 4), but as per the problem requirement, we return the second middle node, which is 4.

Approach:

One of the most efficient ways to solve this problem is by using the Tortoise and Hare Algorithm (also known as the Fast and Slow Pointer approach).

Tortoise and Hare Algorithm (Fast & Slow Pointers):

Idea:

• Maintain two pointers:
  • Slow pointer (tortoise) moves 1 step at a time.
  • Fast pointer (hare) moves 2 steps at a time.
• When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.

Why it works:
The fast pointer moves twice as fast as the slow pointer.
By the time the fast pointer has traversed the entire list, the slow pointer will have covered half the distance, hence pointing to the middle.

Code:

public ListNode middleNode(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;

    while (fast != null && fast.next != null) {
        fast = fast.next.next; // fast moves 2 steps
        slow = slow.next;      // slow moves 1 step
    }

    return slow; // Slow will be at middle
}

Step-by-Step Example Walkthrough:

Consider the list:
1 → 2 → 3 → 4 → 5

Time & Space Complexity:

• Time Complexity: O(n) — We traverse the list only once.
• Space Complexity: O(1) — No extra space used apart from two pointers.

Final Thoughts:

• This approach is optimal because it finds the middle in one pass.
• It works perfectly for both odd and even length linked lists.
• The Tortoise and Hare technique is also widely used in:
  • Cycle detection in linked lists
  • Finding the k-th node from the end
  • Splitting lists into halves

---

Q 2. Remove Nth Node From End of List:

Given the head of a linked list and an integer n, remove the n-th node from the end of the list and return its head.

Example:

Input:
List: 1 → 2 → 3 → 4 → 5
n = 2

Output:
1 → 2 → 3 → 5

Explanation:
The 2nd node from the end is 4, so we remove it and link 3 directly to 5.

Approach 1: Length Method

Idea:

1. First, calculate the length of the linked list.
2. Find the position of the node to remove from the start: position = size - n.
3. Traverse again until that position and remove the target node.

Code:

// Length Method
private static Node removeNthFromEnd(Node head, int n) {
    if (head == null || head.next == null) {
        return null;
    }

    int size = findLength(head);
    if (size == n) {
        return head.next;
    }

    int k = size - n;
    Node temp = head;
    while (temp != null) {
        k--;
        if (k == 0) {
            temp.next = temp.next.next;
            break;
        }
        temp = temp.next;
    }

    return head;
}

private static int findLength(Node head) {
    Node temp = head;
    int count = 0;
    while (temp != null) {
        count++;
        temp = temp.next;
    }
    return count;
}

Time & Space Complexity:

• Time Complexity: O(L)
  O(L) to find the length and O(L) to reach the (size - n)th node → Total O(L)

• Space Complexity: O(1)
  No extra space is used.

Approach 2: Fast & Slow Pointer Method

Idea:

• Move the fast pointer n steps ahead.
• If fast becomes null, it means the head is the node to be removed.
• Otherwise, move both fast and slow pointers forward until fast.next is null.
• Remove the node after the slow pointer.

Code:

// Fast & Slow Pointer Method
private static Node removeNthFromEnd(Node head, int n) {
    if (head == null || head.next == null) {
        return null;
    }

    Node fast = head;
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    if (fast == null) {
        return head.next;
    }

    Node slow = head;
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }

    slow.next = slow.next.next;

    return head;
}

Time & Space Complexity:

• Time Complexity
  O(L) — Single traversal to find and remove the node.

• Space Complexity
  O(1) — No extra space used.

Final Thoughts:

• The Length Method is easier to understand but requires two passes through the list.
• The Fast & Slow Pointer Method is more optimal as it removes the node in one pass.
• The Fast & Slow technique is also used in:
  • Detecting cycles in linked lists
  • Finding middle nodes
  • Merging sorted lists efficiently

---

Q 3. Reverse Linked List – Recursive Approach:

Given the head of a singly linked list, reverse the list using recursion and return the new head of the reversed list.

Example:

Consider the list:
1 → 2 → 3 → 4 → 5

Reversing it will result in:
5 → 4 → 3 → 2 → 1

Thought Process:

• This recursive approach works by breaking down the problem into smaller subproblems.
• It reverses the linked list from the end towards the beginning by recursively processing the rest of the list, then flipping the pointers to reverse the direction between nodes.
• Essentially, the function keeps calling itself with the next node until it reaches the end of the list (the base case).
• During the return phase, it reverses the pointers step-by-step, effectively rebuilding the list in reverse order.
• This technique leverages the call stack to handle the reversal naturally without the need for explicit iteration or extra data structures.

Approach:

• Base Case: If the list is empty (head == null) or has only one node (head.next == null), return the head because the reversed list is the same.
• Recursive Step:
  • Recursively reverse the rest of the list starting from head.next.
  • Once the recursion returns the new head (newHead), point the next node’s next pointer back to the current node (head.next.next = head).
  • Disconnect the current node from its next (head.next = null) to avoid cycles.
• Finally, return newHead, which points to the new head of the reversed list.

Code:

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

    ListNode newHead = reverseList(head.next);

    head.next.next = head;
    head.next = null;

    return newHead;
}

Time & Space Complexity:

• Time Complexity: O(n)
  Each node is visited once during the recursion.

• Space Complexity: O(n)
  The recursion stack will hold up to n calls for a list of length n.

Final Thoughts:

• Recursive reversal elegantly reverses the list by flipping pointers during the return phase of recursion.
• It uses call stack space proportional to the length of the list, which could be a limitation for very long lists.
• This method complements iterative reversal techniques and deepens understanding of recursion and linked list pointer manipulation.

---

Q 4. Reverse Linked List — Iterative Approach:

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

Example:

Consider the list:
1 → 2 → 3 → 4 → 5

After reversing iteratively, the list becomes:
5 → 4 → 3 → 2 → 1

Approach:

• Initialize two pointers: prev as null and curr as the head of the list.
• Iterate through the list until curr becomes null:
  • Store the next node (curr.next) in a temporary variable next.
  • Reverse the current node’s pointer by setting curr.next to prev.
  • Move prev to the current node.
  • Move curr to the next node stored earlier.
• When the loop ends, prev points to the new head of the reversed list.
• Return prev.

This approach reverses the linked list in-place by changing the direction of the pointers while traversing the list once.

Code:

public ListNode reverseList(ListNode head) {
    ListNode curr = head;
    ListNode prev = null;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Time & Space Complexity:

• Time Complexity: O(n)
  We traverse the entire list once, visiting each node exactly one time.

• Space Complexity: O(1)
  The reversal is done in-place with only a few pointers; no extra space is used.

Final Thoughts:

• The iterative method is efficient and avoids the overhead of recursion.
• It reverses the list in one pass using constant space.
• Understanding this approach builds a strong foundation in pointer manipulation, which is key for many linked list problems.

---

5. What's next:

I’m excited to keep growing and sharing along the way! Here’s what’s coming up:

• Posting new blog updates every 3 days to share what I’m learning and building.
• Alongside mastering DSA concepts, I’m also documenting my web development journey — check out my ongoing Web dev Journey Blog for ReactJS concepts, UI projects, Codes, and more.
• Sharing regular progress and insights on X (Twitter) — feel free to follow me there and join the conversation!

Thanks for being part of this journey!

---

6. Conclusion:

In this blog of my dsa journey, I covered four essential linked list problems that are fundamental to mastering Data Structures and Algorithms:

• Finding the Middle of a Linked List using the Tortoise and Hare approach, which efficiently finds the middle node in a single pass.
• Removing the Nth Node from the End with two approaches — the Length Method and the Fast & Slow Pointer Method — highlighting trade-offs between simplicity and efficiency.
• Reversing a Linked List Recursively, which leverages the call stack to elegantly reverse the pointers in a natural, intuitive way.
• Reversing a Linked List Iteratively, which performs the reversal in-place with constant space and is often preferred for its efficiency.

These problems not only strengthen my understanding of linked list traversal and pointer manipulation but also introduce important algorithmic techniques like two-pointer strategies and recursion.

Mastering these concepts will build a strong foundation for tackling more complex linked list challenges and deepen my problem-solving skills in DSA.

If you're on a similar learning path, feel free to follow along or reach out — let’s grow together.