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