[Leetcode]876. Middle of the Linked List

📄 Description

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.

💡 Solutions

1. Using Two Pointers

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

        
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast=head, head
        
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
        return slow

🔎 Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Runtime: 46 ms
Memory: 13.9 MB

How it works

• shift the slow pointer by one
• shift the fast pointer by two (going twice as fast as the slow pointer)

📌 the fast pointer will hit the end of the linked list the same time the slow pointer will reach the middle of the linked list

2. Using Recursion Method

References
https://leetcode.com/problems/middle-of-the-linked-list/
https://leetcode.com/problems/middle-of-the-linked-list/discuss/1837710/Easy-Python-solution-using-two-pointers