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. Q: What is the minimum and maximum length of the linked list?
   • A: The linked list has at least 1 node and at most 100 nodes.
2. Q: Can we modify the linked list?
   • A: No, modifying the linked list is not allowed.
3. Q: What should be returned?
   • A: A reference to the middle node in the singly linked list.

Strategy

We can solve this problem using a two-pointer approach:

• Initialize two pointers, slow and fast, both set to the head of the linked list.
• Move slow by one step and fast by two steps in each iteration.
• When fast reaches the end of the list (or the node before the end in the case of even length lists), slow will be at the middle node.

Code

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
}

Explanation

1. Initialization: Both slow and fast pointers are initialized to point to the head of the linked list.
2. Traversal:
   • The while loop checks whether fast and fast.next are not null.
   • Inside the loop, slow moves one step each time (slow = slow.next).
   • fast moves two steps each time (fast = fast.next.next).
3. Termination: When fast or fast.next is null, slow will be at the middle node of the linked list.
4. Return: The function returns the slow pointer, which now points to the middle node.

Time Complexity

• Time Complexity: O(n) where n is the number of nodes in the linked list. This is because in the worst case, we traverse the linked list once.
• Space Complexity: O(1) since we use only two pointers regardless of the size of the input linked list.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?