Leetcode 876: Middle of the Linked List

Input: The input is a singly linked list with nodes containing integer values.

Example: Input: head = [1, 2, 3, 4, 5]

Constraints:

• 1 <= number of nodes <= 100

• 1 <= Node.val <= 100

Output: Return the middle node of the linked list. If the list has two middle nodes, return the second one.

Example: Output: [3, 4, 5]

Constraints:

• The output should be the list starting from the middle node.

Goal: The goal is to determine the middle node of the linked list using a two-pointer approach.

Steps:

• Use two pointers, 'slow' and 'fast'. Initialize both to the head of the list.

• Move the 'slow' pointer one step at a time, and the 'fast' pointer two steps at a time.

• When the 'fast' pointer reaches the end of the list, the 'slow' pointer will be at the middle node.

Goal: The solution must efficiently handle lists of varying lengths within the given constraints.

Steps:

• The list contains between 1 and 100 nodes.

• Each node contains an integer between 1 and 100.

Assumptions:

• The linked list is non-empty and contains at least one node.

• The linked list may have an even or odd number of nodes.

• Input: Input: head = [1, 2, 3, 4, 5]

• Explanation: The list has 5 nodes. The middle node is 3, so the output will be the sublist starting from node 3: [3, 4, 5].

• Input: Input: head = [1, 2, 3, 4, 5, 6]

• Explanation: The list has 6 nodes. The two middle nodes are 3 and 4, and since the second middle node should be returned, the output will be the sublist starting from node 4: [4, 5, 6].

Approach: We can use the two-pointer technique to efficiently find the middle node of the linked list. The 'slow' pointer will move one step at a time, while the 'fast' pointer will move two steps at a time. When the fast pointer reaches the end, the slow pointer will be at the middle node.

Observations:

• The two-pointer technique is optimal for this problem as it allows us to traverse the list in a single pass while keeping track of the middle node.

• The method ensures that we can handle lists with both even and odd numbers of nodes.

Steps:

• Initialize two pointers, slow and fast, both pointing to the head of the list.

• Move slow by one step and fast by two steps in each iteration.

• When fast reaches the end of the list, slow will be at the middle node.

Empty Inputs:

• If the list is empty (no nodes), return null or handle as an edge case.

Large Inputs:

• The solution should efficiently handle up to 100 nodes.

Special Values:

• If the list has only one node, the middle node is that node itself.

Constraints:

• Ensure that the solution works for both even and odd-length lists.

ListNode* middleNode(ListNode* head) {
    ListNode* slow = head, *fast = head;
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    // if(!fast)
        // return slow->next;
    return slow;
}

1 : Function Definition

ListNode* middleNode(ListNode* head) {

The function `middleNode` takes a pointer to the head of a singly linked list and returns a pointer to the middle node of the list.

2 : Pointer Initialization

    ListNode* slow = head, *fast = head;

Two pointers, `slow` and `fast`, are initialized to the head of the list. The `slow` pointer moves one node at a time, while the `fast` pointer moves two nodes at a time.

3 : While Loop

    while(fast && fast->next) {

A `while` loop is used to traverse the list. The loop continues as long as the `fast` pointer and the `fast->next` pointer are not null.

4 : Pointer Movement

        slow = slow->next;

The `slow` pointer moves one step forward by advancing to the next node in the list.

5 : Pointer Movement

        fast = fast->next->next;

The `fast` pointer moves two steps forward by advancing to the next node twice, skipping one node in between.

6 : Return Statement

    return slow;

After the loop finishes, the `slow` pointer is returned, which points to the middle node of the list.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), where n is the number of nodes in the list, as we need to traverse the list once.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1), as we only use a constant amount of extra space for the two pointers.

Leetcode 876: Middle of the Linked List

Explore →