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

この記事は約5分で読めます。

 

問題

原文

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:

 

■連結リストについて

連結リスト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

 

補足・参考・感想

参考 ※以下の2サイトはとてもわかりやすかった

↓ListNodeの中身とLeetcodeでの連結リストのinputについて

LeetCodeの入出力値の型に騙されるな – 206. Reverse Linked List – Qiita

↓LeetCodeでの連結リストの問題パターン

連結リストのちょっとした問題集 (zenn.dev)

 

連結リストの扱いに慣れなくて難しい。連結リストをListNodeで扱うのはLeetCodeに特有なのか一般的なのか調べてみた方が良いかもしれない。

しばらくは連結リストの問題を集中的に解いてみる。

 

前:217. Contains Duplicate

次:1290. Convert Binary Number in a Linked List to Integer

LeetCode 解答・解説記事一覧

コメント