algoadvance

Leetcode 876. Middle of the Linked List

Problem Statement

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.

Clarifying Questions

  1. Input Format: Is the input provided as a linked list or as some other data structure?
    • Input is provided as a singly linked list.
  2. Edge Cases: What is the minimum and maximum length of the linked list?
    • The minimum length is 1 (i.e., the list is not empty), and there is no explicit maximum length mentioned.
  3. Output Format: What should be the format of the output?
    • The output should be the middle node of the given linked list.

Strategy

We will use the two-pointer technique to solve this problem efficiently:

  1. Initialize two pointers, slow and fast, both pointing at the head of the linked list.
  2. Move the slow pointer one step at a time.
  3. Move the fast pointer two steps at a time.
  4. When the fast pointer reaches the end of the list, the slow pointer will be at the middle of the list.

By using this approach, we are able to find the middle node in a single traversal of the linked list.

Code

#include <iostream>

// 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;
        
        // Move fast pointer two steps and slow pointer one step each time
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        return slow;
    }
};

Time Complexity

The time complexity for this solution is (O(n)), where (n) is the number of nodes in the linked list. This is because we are traversing the list only once.

The space complexity is (O(1)) since we are using a constant amount of extra space for the two pointers.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI