Middle of the Linked List — LeetCode 876 Python Solution

The problem

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

Input

head = [1,2,3,4,5]

Output

[3,4,5]

Explanation

The middle node of the list is node 3.

Python solution

# 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: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        return slow

Complexity

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 876. Middle of the Linked List is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Linked List.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Related problems