0876. Middle of the Linked List

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.

Constraints:

• The number of nodes in the list is in the range [1, 100].
• 1 <= Node.val <= 100

Analysis

This question can be solved by two pointers: one pointer moves one step each turn and the other moves two steps, so when the fast pointer has reached to the end of the linkedlist, the slow pointer will be at the middle of the linkedlist. Since we want to return the second middle pointer from the linkedlist, we need to make sure the fast pointer is pointing to the next, which is null, of the last pointer.

• Time: $O(n / 2)$ or $O(n)$
• Space: $O(1)$

Code

/**
 * 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 *a = head, *b = head;
        while (b && b -> next) {
            a = a -> next;
            b = b -> next -> next;
        }
        return a;
    }
};

---

Last update: April 1, 2022