◻️876. Middle of the Linked List (easy)

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.

---

Solutions

Brute Force

Runtime 0 ms Memory 9.17 MB

T.C -> O(n+ n/2) | S.C -> O(1)

/**
 * 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) {}
 * };
 */

// Brute Force

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* ptr = head;
        int cnt=0;

        while(ptr != nullptr){    // T.C -> O(n)
            cnt+=1;
            ptr=ptr->next;
        }
        ptr = head;
        cnt = (cnt/2)+1;
        while(true){              // T.C -> O(n/2)
            cnt--;
            if(cnt==0) break;
            ptr=ptr->next;
        }
        return ptr; 
    }
};

Optimised - Fast ptr & Slow ptr

Runtime 4 ms Memory 9.26 MB

T.C -> O(n/2) | S.C -> O(1)

/**
 * 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) {
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast != nullptr && fast->next != nullptr){ // in odd no. of n, fast pointer will go to last and in even no. of n, fast pointer will go to null as in even the first pointer points to index 1 and goes odd steps - 1,3,5...
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow; 
        }
};