Middle of the Linked List

13 May 2026 0 Likes

Problem Description

Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.
Example 1:
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the linked list is: 3. Therefore, the returned linked list starts from node 3.
Example 2:
Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: The linked list contains two middle nodes: 3 and 4. According to the problem statement, we return the second middle node, which is: 4.
Example 3:
Input: head = [1]
Output: [1]
Explanation: The linked list contains only one node, so that node itself becomes the middle node.

Constraints

1. The linked list contains at least 1 node.
2. The number of nodes may vary depending on platform limits.
3. If the linked list contains an even number of nodes, the second middle node should be returned.
4. Efficient solutions are expected to traverse the linked list in linear time using constant extra space.

Understanding the Problem

The problem asks us to find the middle node of a singly linked list. Since linked lists do not support direct index access like arrays, we must traverse the nodes sequentially.

One straightforward way to solve the problem is to first count the total number of nodes and then move to the middle position.

For example, in [1,2,3,4,5], the total number of nodes is 5. The middle position becomes 5 / 2 = 2, which corresponds to node 3.

Now consider [1,2,3,4,5,6]. In this case, the linked list contains two middle nodes: 3 and 4. The problem specifically requires us to return the second middle node, which is node 4.

Hints

The first hint is to think about traversing the linked list at different speeds. A highly efficient technique uses one slow pointer and one fast pointer.

The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. By the time the fast pointer reaches the end of the linked list, the slow pointer naturally reaches the middle node.

This approach eliminates the need to count nodes separately and solves the problem in a single traversal.

Solutions

OPTIMAL

Fast and Slow Pointer Middle Node Solution

This approach uses the fast and slow pointer technique to efficiently locate the middle node of the linked list in a single traversal.

Two pointers are maintained: slow, which moves one step at a time, and fast, which moves two steps at a time. Initially, both pointers start at the head of the linked list.

As the traversal continues, the fast pointer progresses twice as quickly as the slow pointer. By the time the fast pointer reaches the end of the linked list, the slow pointer naturally reaches the middle node.

For example, in [1,2,3,4,5], the traversal becomes: slow → 1 → 2 → 3 and fast → 1 → 3 → 5. When the fast pointer reaches the end, the slow pointer is positioned at node 3, which is the middle node.

For even-sized linked lists such as [1,2,3,4,5,6], the slow pointer automatically lands on the second middle node, which satisfies the problem requirement.
public class D1_MiddleOfTheLinkedList {

    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;
    }

    private class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def middleNode(self, head):
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        return slow
Time Complexity
O(n)
Space Complexity
O(1)

Conclusion

The Middle of the Linked List problem is a classic linked list problem that introduces the powerful fast and slow pointer technique. The problem demonstrates how different traversal speeds can efficiently locate important positions inside linked lists without additional memory.

Mastering this problem helps build a strong understanding of pointer traversal, linked list manipulation, and single-pass optimization techniques, which are commonly used in coding interviews and real-world data structure problems.

💬 Comments