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.

Example:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Approach: We can do it in two passes where in first iteration we can get the number of nodes and in the second iteration we will get the size/2th node. 

Let's try to reduce the number of iterations. What we can do, we can use two pointers; one is slow which goes 1 step at one time and one is fast which goes 2 steps at a time:

• slow = slow.next
• fast = fast.next.next

Obviously when fast is null or it's next is null, slow will be pointing at the middle node. That's all!

Implementation in C#:

    public ListNode MiddleNode(ListNode head)

    {

        if (head == null || head.next == null)

        {

            return head;

        }

        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null)

        {

            slow = slow.next;

            fast = fast.next.next;

        }

        return slow;

    }

Complexity: O(n)