8.Middle of the Linked List

Solution I

class Solution
{
public:
    ListNode *middleNode(ListNode *head)
    {

        if (head == NULL)
        {
            return head;
        }

        ListNode *p = head;
        ListNode *q = head;
        int s = 0;
        while (p != NULL)
        {
            s = s + 1;
            p = p->next;
        }

        int mid = s / 2;

        int i = 0;
        while (i < mid)
        {
            i++;
            q = q->next;
        }
        cout << q->val;
        return q;
    }
}

This approach has a time complexity of O(n) but we need to iterate the list a number of times.

Solution II (Using two pointers)

class Solution
{
public:
    ListNode *middleNode(ListNode *head)
    {

        ListNode *p = head;
        ListNode *q = head;

        while (p!= NULL && p->next != NULL)
        {
            p = p->next->next;
            q = q->next;
        }
        
        return q;
    }
};

This solution is using fast pointer and slow pointer. Time Complexity O(n).