Middle of a Linked List

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Floyd's slow/fast pointer: slow advances one step, fast advances two. When fast reaches end, slow is at middle.

Algorithm

1slow = fast = head.
2While fast != null and fast.next != null: slow = slow.next; fast = fast.next.next.
3Return slow.

Common Pitfalls

•For even length lists, this returns the second middle. Adjust termination condition if first middle is needed.

Middle of a Linked List.java

Java

// Approach: Slow/fast pointer technique. When fast reaches end, slow is at middle.
// Time: O(n) Space: O(1)
class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

class Solution {
    int getMiddle(Node head) {
        Node slow = head;
        Node fast = head;

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

        return slow.data;
    }
}

Was this solution helpful?