【LeetCode】876. Middle of the Linked List 解答・解説【Python】

問題
1. 原文
2. 内容
方針
解答
1. 解答1：
補足・参考・感想

問題

原文

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 1:

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

　Output: [3,4,5]

　Explanation: The middle node of the list is node 3.

Example 2:

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

Output: [4,5,6]

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

Constraints:

The number of nodes in the list is in the range [1, 100].

1 <= Node.val <= 100

内容

単方向連結リストheadが与えられます。連結リストの中央のノードを返してください。

もし、中央のノードが2つある場合は2つ目のノードを返してください。

※正しくない可能性があります。

方針

・2ポインタを使用

解答

解答1：

#slow,fast pointer
#slowは1、fastは2進む。fast pointerが終端にたどりついたらslow pointerは中央に位置している
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            print("fast                 ",fast)
            print("fast.next            ",fast.next.next)
            slow = slow.next
            fast = fast.next.next
        return slow

#slow,fast pointer

#slowは1、fastは2進む。fast pointerが終端にたどりついたらslow pointerは中央に位置している

class Solution:

def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:

slow = fast = head

while fast and fast.next:

print("fast ",fast)

print("fast.next ",fast.next.next)

slow = slow.next

fast = fast.next.next

return slow

■連結リストについて

連結リストheadの中身は↓こちら。

ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}}}

headの終端(5)には[val=5,next=None]がある。

headの終端ひとつ手前(4)は、[val=4, next=[val=5,next=None]]

下線部はheadの終端(5)を含んでいる。

↑こちらのように、headの各ノードは次ノード以降を含む入れ子のような構造。

各ノードはListNodeクラスとして書かれているのでprintしてみると何となくとっつきにくい形になっているようだった。

■解答

↓以下の2つのポインタを使用する

・リストを1つ進むslow pointer

・リストを2つ進むfast pointer

slow pointerは連結リストを1つずつ進む。

fast pointerはslow pointerの2倍の速さで連結リストを進んでいく。

fast pointerが終端に到達したとき、slow pointerはリスト内の中央の位置にある。

fast pointerはListNode内のnextを利用して↓こちらのように更新する

fast.next.next　※これで2つ先のノードを指定

連結リストの要素数が偶数の時、動作のイメージがわかなかったのでテストケースを使って考えてみる。↓

・例1：head = [1,2,3,4,5]

➀slow=1, fast=1, slow.next=2, fast.next.next=3

②slow=2, fast=3, slow.next=3, fast.next.next=5

③slow=3, fast=5, slow.next=4, fast.next.next=なし

fast(つまり5)の次ノードは存在せず、fast.nextも存在しないので③はWhile節は処理しない。

slowを返して終了→slow=2、headの2番目(0-index)の値は3

例2：head = [1,2,3,4,5,6]

➀slow=1, fast=1, slow.next=2, fast.next.next=3

②slow=2, fast=3, slow.next=3, fast.next.next=5

③slow=3, fast=5, slow.next=4, fast.next.next=None

※例1とは違い、headの終端(6)はそのnext属性にNoneがあるので、While

④slow=4, fast=None, slow.next=5, fast.next.next=なし

fastの次のノードが存在せず、fast.nextも存在しないので④は処理しない。

slowを返して終了→slow=3, headの3番目(0-index)の値は4