Middle of the Linked List

# 問題

次のように定義される連結リストが与えられたときに，真ん中の値はなにか計算する関数を書け．

1
2
3
4
5
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

例

1
2
head = [1] -> [2] -> [3] -> [4] -> [5],        ans = [3] -> [4] -> [5]
head = [1] -> [2] -> [3] -> [4] -> [5] -> [6], ans = [4] -> [5] -> [6]

# 解法

🐰と🐢テクニック
- 二倍の速度で動く🐰を端まで走らせると🐢は真ん中ぐらいにまだいる
whileのループの条件は，ループ内部の実行時エラーが発生しない条件を考えれば良い．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
# 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]:
        if head == None:
            return []
        faster = head
        slower = head
        while faster is not None and faster.next is not None:
            faster = faster.next.next
            slower = slower.next
        return slower

# 出典

https://leetcode.com/problems/middle-of-the-linked-list/