Retrieve middle node of a singly linked list

Question: find the middle node in a singly linked list. If the linked list has even number of nodes, return either of the middle nodes. For example, 1->2->3 returns 2 but 1->2->3->4 returns either 2 or 3.

This is a common algorithm concerning linked lists. The trick here is to have two pointers moving at different paces. When the faster pointer reaches the end of the list, the slow pointer is pointing to the middle node in the list. Here is the algorithm implemented in C++:

#include<iostream>
using namespace std;

struct Node
{
  Node *next;
  int data;
};

Node* findMidofLinkedList(Node* head)
{
  Node *fast = head;
  Node *slow = head;

  while (fast->next != NULL && fast->next->next != NULL)
  {
    fast = fast->next->next;
    slow = slow->next;
  }

  return slow;
}

Explanation: We maintain two pointers fast and slow. For every iteration of the while loop, we move the fast pointer two nodes forward and move the slow pointer one node forward. When the node next to the fast pointer is NULL or when the node next to the next node of the fast pointer is NULL, the slow pointer has reached the middle node. We simply returns the slow pointer.

Example: Let's trace our algorithm with this linked list 1->2->3->4->5:

1. First iteration: fast points to 3. slow points to 2. fast->next is 4. fast->next->next is 5.
2. Second iteration: fast points to 5. slow points to 3. fast->next is NULL. fast->next->next is NULL. So we stop after this iteration. Slow is now pointing at 3 which is the middle node.