The Middle of a Linked List

Problem Statement

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.

Approach

We will initialise two pointers, slow and fast with the head of the linked list. Then, move the fast pointer by two steps and the slow pointer by one. When fast reaches NULL, slow will point to the middle of the list. This is popularly known as the tortoise algorithm.

Note: We move the pointers forward as fast = fast->next. fast++ will not work here because nodes are not allocated at contiguous memory locations.

Tip: Before moving the pointer forward, make sure it is not NULL. This is because we can not move the NULL pointer forward.

Dry Run

Initialise fast and slow pointers with the head of the list.

When fast moves forward by two steps, slow moves by one step.

Fast moves two steps, slow moves one.

As we increment the fast pointer by one, it becomes NULL. Thus at this point, slow points to the middle node.

Code

/**
 * 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) {
        if(head==nullptr || head->next == nullptr)  
            return head;

        ListNode* slow = head;
        ListNode* fast = head;

        while(fast != nullptr){
            fast = fast->next;
            if(fast != nullptr){
                fast = fast->next;
                slow = slow->next;
            }
        }
        return slow;
    }
};