Middle of the Linked List

Share

Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes (even length list), return the second middle node.

Example 1
Input: head = [1, 2, 3, 4, 5]
Output: [3, 4, 5]
Explanation: The middle node has value 3. Returning node 3 and everything after it.
Example 2
Input: head = [1, 2, 3, 4, 5, 6]
Output: [4, 5, 6]
Explanation: With 6 nodes there are two middle nodes (3 and 4). The second middle node (value 4) is returned.

Solution Approach - Slow and Fast Pointer

The classic approach is to use two pointers where slow moves one step at a time and fast moves two steps at a time. When fast reaches the end, slow is at the middle.

  • Initialize both slow and fast at head.
  • While fast != null and fast.next != null, advance slow by 1 and fast by 2.
  • When the loop ends, slow is at the middle node. For even-length lists, this naturally gives the second middle.
  • Return slow.
Java
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class MiddleOfLinkedList {

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

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

        return slow; // slow is at the middle
    }
}
Complexity Analysis:

Time complexity: O(n) where n is the number of nodes. The fast pointer traverses the list in n/2 iterations.
Space complexity: O(1) since only two pointer variables are used.