Middle of the Linked List

main.md

Middle of the Linked List

Question on Leetcode - Easy

Approach

The approach I took was to use two pointers. One moved the normal speed, while the other went twice as fast as the first pointer.

When the faster pointer reaches the end, it returns the value (node) of the value at that time.

Code

# 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 = head
        fast = head
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
        return slow

Complexities

• Time complexity: O(n)
• Space complexity: O(1)