Find the middle of LinkedList

Problem Overview

The problem "Middle of the Linked List" requires finding the middle node of a singly linked list. If the list has an even number of nodes, the problem specifies to return the second of the two middle nodes. This is a popular problem for practicing linked list traversal and understanding the two-pointer technique.

URL: Middle of the Linked List

Understanding the Problem

Given a singly linked list, the task is to find and return the middle node. The important detail to note is that if the list has an even number of elements, we should return the node that comes after the first middle node.

Example

Input: Linked List: 1 -> 2 -> 3 -> 4 -> 5

Output: Node with value 3

For the list 1 -> 2 -> 3 -> 4 -> 5 -> 6, since there are two middle nodes (3 and 4), we return 4.

Key DSA Concepts and Theory

Linked List

A linked list is a linear data structure consisting of nodes. Each node holds data and a reference (or link) to the next node in the sequence. The list is accessed starting from the head node, and traversal continues until it meets NULL, indicating the end of the list. Key characteristics of linked lists include dynamic memory allocation and efficient insertions/deletions.

Two-Pointer Technique

This technique is an elegant way of traversing a sequence/linked list with two pointers moving at different speeds. Often used in linked lists, it helps solve various problems with minimal space overhead. In this problem, the slow and fast pointers method allows us to efficiently find the middle of a linked list.

Solution Approach

The optimal solution employs the two-pointer technique, specifically the Slow and Fast Pointer approach:

• Slow Pointer: Moves by one step.
• Fast Pointer: Moves by two steps.

When the fast pointer reaches the end of the list, the slow pointer will be at the middle.

Step-by-Step Explanation

1. Initialize: Set slow and fast pointers to the head of the list.
2. Traverse the List: Move slow one step and fast two steps in each iteration.
3. Find the Middle: When fast reaches the end (NULL) or the node before the end (fast.next == NULL), slow will be positioned at the middle node.

C++ Code Example

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        return slow;
    }
};

Java Code Example

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
}

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes in the linked list. Each node is visited at most once.
• Space Complexity: O(1), since no extra data structures are used, and only pointers are utilized.

Common Mistakes to Avoid

1. Incorrect Initialization: Always initialize both pointers to the head.
2. Loop Condition: Ensure the loop checks both fast and fast.next to avoid null pointer exceptions.
3. Returning the Middle: For even length lists, ensure the correct middle node is returned (i.e., the second in case of two middles).

Similar Problems on LeetCode

• Merge Two Sorted Lists (Problem 21)
• Reverse Linked List (Problem 206)
• Remove N-th Node From End of List (Problem 19)

Additional Resources and References

• GeeksforGeeks Linked List Introduction
• Techie Delight on Two-Pointer Techniques

This article provides a clear understanding of how to find the middle of a linked list using the two-pointer technique, clarifying each step with examples and code in C++ and Java.