876. Middle of the Linked List
给你一个 linked list 的 head node，要你回传它正中间的 node
如果长度是偶数就回传靠后的那个
Example 1:
Input: head = [1,2,3,4,5]
Output: [3,4,5]
(回传 3 那个 node)
Example 2:
Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
(回传 4 那个 node)
思路:
1. linked list 题目中 fast/slow node 的最基本型
让 fast, slow 都从 head 开始 每次让 fast = fast.next.next, slow = slow.next
就可以在 fast 走到最尾端时让 slow 在正中间
2.
Python 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, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow