Middle of the Linked List

Problem

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.

Constraints

• The number of nodes in the list is in the range [1, 100].
• 1 <= Node.val <= 100

Solution

The problem Middle of the Linked List can be solved using two pointers. When the pointer hare is set to move twice as fast as the pointer turtle, turtle will be pointing to the middle of the linked list when hare reaches the end of the list.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
  public:
    ListNode *middleNode(ListNode *head)
    {
        ListNode *turtle = head;
        ListNode *hare = head;

        while (hare && hare->next)
        {
            turtle = turtle->next;
            hare = hare->next->next;
        }

        return turtle;
    }
};