[LeetCode&Python] Problem 876. Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]

Output: Node 3 from this list (Serialization: [3,4,5])

The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).

Note that we returned a ListNode object ans, such that:

ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

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

Output: Node 4 from this list (Serialization: [4,5,6])

Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:

The number of nodes in the given list will be between 1 and 100.

We can use two trappers 'slow' and 'fast' to help us to find the answer.

Each time, 'slow' will jump to the next node and 'fast' will jump to the next two nodes.

When 'fast' or 'fast.node' reaches the end node, 'slow' reaches the answer.

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution:

    def middleNode(self, head):

        """

        :type head: ListNode

        :rtype: ListNode

        """

        slow=fast=head

        while fast and fast.next:

            slow=slow.next

            fast=fast.next.next

        return slow

巴特西

[LeetCode&Python] Problem 876. Middle of the Linked List

最新文章

热门文章