Middle Element Finder

Problem Statement

Write a Java program that finds the middle element of a singly linked list in a single pass using the fast-and-slow pointer technique. The linked list consists of nodes, each containing an integer value and a reference to the next node. For lists with an odd number of nodes, return the middle node’s value; for even-length lists, return the value of the second middle node (e.g., in 1→2→3→4, return 3). The program should handle edge cases like empty lists and single-node lists. Test the implementation with linked lists of varying sizes, including empty lists, single-node lists, and lists with odd and even lengths. You can visualize this as finding the middle card in a chain of numbered cards, using two pointers where one moves twice as fast to reach the middle efficiently.

Input:

• A singly linked list of integers (e.g., 1→2→3→4→5). Output: The value of the middle node as an integer, or -1 if the list is empty (e.g., 3 for 1→2→3→4→5). Constraints:
• The list size is between 0 and 10^5.
• Node values are integers in the range [-10^9, 10^9].
• The list may be empty. Example:
• Input: 1→2→3→4→5
• Output: 3
• Explanation: Middle node of 5 nodes is the 3rd node (value 3).
• Input: 1→2→3→4
• Output: 3
• Explanation: Second middle node of 4 nodes is the 3rd node (value 3).
• Input: []
• Output: -1
• Explanation: Empty list returns -1.

Pseudocode

CLASS Node
    SET value to integer
    SET next to Node (null by default)
ENDCLASS

FUNCTION findMiddle(head)
    IF head is null THEN
        RETURN -1
    ENDIF
    SET slow to head
    SET fast to head
    WHILE fast is not null AND fast.next is not null
        SET slow to slow.next
        SET fast to fast.next.next
    ENDWHILE
    RETURN slow.value
ENDFUNCTION

FUNCTION toString(head)
    IF head is null THEN
        RETURN "[]"
    ENDIF
    CREATE result as new StringBuilder
    SET current to head
    WHILE current is not null
        APPEND current.value to result
        IF current.next is not null THEN
            APPEND " " to result
        ENDIF
        SET current to current.next
    ENDWHILE
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of linked lists
    FOR each testCase in testCases
        PRINT test case details
        CALL findMiddle(testCase.head)
        PRINT middle element
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define a Node class with: a. An integer value. b. A next pointer to the next node.
2. In findMiddle: a. If head is null, return -1 (empty list). b. Initialize slow and fast pointers to head. c. While fast and fast.next are not null:
   • Move slow one step, fast two steps. d. When fast reaches the end, slow is at the middle node. e. Return slow.value.
3. In toString: a. If head is null, return "[]". b. Traverse the list, append each value to a StringBuilder with spaces. c. Return the string representation.
4. In main, test with empty, single-node, odd-length, and even-length lists.

Java Implementation

public class MiddleElementFinder {
    // Node class for the linked list
    static class Node {
        int value;
        Node next;

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

    // Finds the middle element using fast-and-slow pointer technique
    public int findMiddle(Node head) {
        if (head == null) {
            return -1;
        }
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow.value;
    }

    // Converts linked list to string for output
    public String toString(Node head) {
        if (head == null) {
            return "[]";
        }
        StringBuilder result = new StringBuilder();
        Node current = head;
        while (current != null) {
            result.append(current.value);
            if (current.next != null) {
                result.append(" ");
            }
            current = current.next;
        }
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        Node head;

        TestCase(int[] values) {
            if (values.length == 0) {
                head = null;
                return;
            }
            head = new Node(values[0]);
            Node current = head;
            for (int i = 1; i < values.length; i++) {
                current.next = new Node(values[i]);
                current = current.next;
            }
        }
    }

    // Main method to test middle element finder
    public static void main(String[] args) {
        MiddleElementFinder finder = new MiddleElementFinder();

        // Test cases
        TestCase[] testCases = {
            new TestCase(new int[]{1, 2, 3, 4, 5}), // Odd length
            new TestCase(new int[]{1, 2, 3, 4}),     // Even length
            new TestCase(new int[]{}),               // Empty list
            new TestCase(new int[]{5}),              // Single node
            new TestCase(new int[]{1, 1, 1, 1, 1, 1}) // Even length with duplicates
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            TestCase test = testCases[i];
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Input list: " + finder.toString(test.head));
            int middle = finder.findMiddle(test.head);
            System.out.println("Middle element: " + middle + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Input list: 1 2 3 4 5
Middle element: 3

Test case 2:
Input list: 1 2 3 4
Middle element: 3

Test case 3:
Input list: []
Middle element: -1

Test case 4:
Input list: 5
Middle element: 5

Test case 5:
Input list: 1 1 1 1 1 1
Middle element: 1

Explanation:

• Test case 1: Odd-length list 1→2→3→4→5, middle is 3rd node (3).
• Test case 2: Even-length list 1→2→3→4, second middle is 3rd node (3).
• Test case 3: Empty list, returns -1.
• Test case 4: Single node 5, returns 5.
• Test case 5: Even-length list 1→1→1→1→1→1, second middle is 4th node (1).

How It Works

• Node: Stores an integer value and a next pointer.
• findMiddle:
  • Returns -1 for empty lists.
  • Uses slow (moves one step) and fast (moves two steps) pointers.
  • When fast reaches the end, slow is at the middle (or second middle for even length).
• toString: Converts the list to a space-separated string, returning "[]" for empty lists.
• Example Trace (Test case 1):
  • Input: 1→2→3→4→5.
  • Initial: slow=1, fast=1.
  • Step 1: slow=2, fast=3.
  • Step 2: slow=3, fast=5.
  • Step 3: fast=null, slow=3.
  • Return: 3.
• Main Method: Tests odd-length, even-length, empty, single-node, and duplicate lists.

Complexity Analysis Table

Note:

• n is the number of nodes in the list.
• Time complexity: O(n) for findMiddle (single pass, fast pointer covers list in n/2 steps); O(n) for toString (traverse list).
• Space complexity: O(1) for findMiddle (two pointers); O(n) for toString (StringBuilder).
• Worst case: O(n) time, O(n) space for output with large lists.

✅ Tip: Use the fast-and-slow pointer technique to find the middle element efficiently in one pass. For even-length lists, choose whether to return the first or second middle node based on problem requirements.

⚠ Warning: Ensure null checks for fast and fast.next to avoid null pointer exceptions. Handle empty lists by returning a sentinel value like -1.