876. Middle of the Linked List - Explanation

Description

You are 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]

Example 2:

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

Output: [4,5,6]

Constraints:

1 <= The length of the list <= 100
1 <= Node.val <= 100

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Convert To Array

# 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]:
        cur = head
        arr = []
        while cur:
            arr.append(cur)
            cur = cur.next
        return arr[len(arr) // 2]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Find Length of the List

# 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]:
        n, cur = 0, head
        while cur:
            cur = cur.next
            n += 1

        n //= 2
        cur = head
        while n:
            n -= 1
            cur = cur.next
        return cur

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

3. Fast & Slow 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

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.