876. Middle of the Linked List

• Link: https://leetcode.com/problems/middle-of-the-linked-list/

Question

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 1:

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

Example 2:

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.

Constraints:

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

Approach 1: Brute Force

Intuition

• Count the no. of nodes
• Return the node at count/2 + 1 index

Algorithm

1. Initialize a count variable with 0
2. Initialize a Node* curr with head
3. Loop through the LL to find the total no. of nodes by incrementing count by 1 in each iteration
4. Initialize curr to head
5. Loop through LL with curr till count / 2
6. Return the curr

Code

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        int count = 0;
        ListNode* curr = head;
        while (curr) {
            curr = curr->next;
            count++;
        }
        curr = head;
        for (int i = 0 ; i < count / 2 ; i++) {
            curr = curr->next;
        }

        return curr;
        
    }
};

Complexity Analysis

• Time Complexity: $O(N+\frac{N}{2})=O(N)$
• Space Complexity: $O(1)$

Approach 2: Optimal

Intuition

• Fast & Slow Pointer

Algorithm

1. Initialize a ListNode* fast & ListNode* slow with head
2. Loop through the LL while fast && fast->next exists
3. slow will increment 1 node at a time & fast will increment 2 nodes at a time
4. After the loop is completed slow pointer will be the middle node

Code

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;

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

        return slow;
    }
};

Complexity Analysis

• Time Complexity: $O\left(\frac{N}{2}\right)=O(N)$
• Space Complexity: $O(1)$