876. Middle of the Linked List.md

876. Middle of the Linked List

1. Description

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:

• The number of nodes in the given list will be between 1 and 100.

2. Solutions

Solution 1: Language: C Fast and Slow Pointers

Move two pointers from the head node of the linked list, until the faster one attach the tail. The speed of the fast pointer is twice of the slow pointer. $V_{fast} = 2 \times V_{slow}$ so we could get $S_{slow} = \frac{1}{2} \times S_{fast}$. After combining with the if statement to determine which node has been returned.

• Sunday, 18 October, 2020
• Time Complexity: $O(n)$
• Space Complexity: $O(1)$
• Runtime: 0 ms, faster than 100.00% of C online submissions for Middle of the Linked List.
• Memory Usage: 6 MB, less than 41.78% of C online submissions for Middle of the Linked List.

/*
Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};
*/

// Fast and slow pointers to obtain the 1/2 route.
struct ListNode *middleNode(struct ListNode *head) {
    struct ListNode *fastPointer = head;
    struct ListNode *slowPointer = head;
    // Because the fast pointer moves to the next two nodes at once, so we need
    // to make sure both of these two nodes are not NULL.
    while (fastPointer->next != NULL && fastPointer->next->next != NULL) {
        fastPointer = fastPointer->next->next;
        slowPointer = slowPointer->next;
    }
    // Return the pointer by parity of the total number of elements.
    if (fastPointer->next != NULL) {
        return slowPointer->next;
    } else {
        return slowPointer;
    }
}