Fast and Slow Pointer to Get the Middle of the Linked List

Given a singly linked list node, return the value of the middle node. If there’s two middle nodes, then return the second one.

Constraints
n ≤ 100,000 where n is the number of nodes in node
Example 1
Input
node = [0, 1, 2]
Output
1

Algorithm to Get Middle of the Linked List

We can solve this problem using fast and slow pointer – let the fast pointer run twice as fast as the slow one, and when the fast reaches the end of the linked list, the slow pointer must be at the middle of the linked list.

The time complexity is O(N) where N is the number of the nodes in the linked list and the space complexity is O(1) constant.

C++ implementation of fast and slow pointer to locate the middle of the linked list:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
int middleOfLinkedList(LLNode* node) {
    if (!node) return -1;
    auto fast = node;
    auto slow = node;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow->val;
}

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
int middleOfLinkedList(LLNode* node) {
    if (!node) return -1;
    auto fast = node;
    auto slow = node;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow->val;
}

Python implementation of the fast and slow pointer that gets the center of the linked list:

1
2
3
4
5
6
7
8
9
10
11
12

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleOfLinkedList(self, node):
        slow = node
        fast = node
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow.val

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleOfLinkedList(self, node):
        slow = node
        fast = node
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow.val

See other implementations of getting the middle of the linked list:

• Fast and Slow Pointer to Get the Middle of the Linked List
• Teaching Kids Programming – Fast and Slow Pointer to Obtain the Middle of the Linked List
• How to Compute the Middle of the Linked List using Fast and Slow Pointer?
• GoLang: Compute the Middle of a Linked List

–EOF (The Ultimate Computing & Technology Blog) —