問題
原文
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:
1 2 3 4 5 6 7 8 9 10 11 |
#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
補足・参考・感想
参考 ※以下の2サイトはとてもわかりやすかった
↓ListNodeの中身とLeetcodeでの連結リストのinputについて
LeetCodeの入出力値の型に騙されるな – 206. Reverse Linked List – Qiita
↓LeetCodeでの連結リストの問題パターン
連結リストの扱いに慣れなくて難しい。連結リストをListNodeで扱うのはLeetCodeに特有なのか一般的なのか調べてみた方が良いかもしれない。
しばらくは連結リストの問題を集中的に解いてみる。
コメント