はじめに
LeetCodeの問題を解答します。
なるべく、問題の和訳と詳細なコメントを書いています。
余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。
様々なカテゴリの問題をランダムにあたる方法も良いですが、
二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。
テーマごとに問題を分類しました。
LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。
また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。
LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。
はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。
問題
原文
Given the
headof 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：Python, two pointer
|
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：Rust two pointer
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// Definition for singly-linked list. // #[derive(PartialEq, Eq, Clone, Debug)] // pub struct ListNode { // pub val: i32, // pub next: Option<Box<ListNode>> // } // // impl ListNode { // #[inline] // fn new(val: i32) -> Self { // ListNode { // next: None, // val // } // } // } impl Solution { pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> { let mut slow = &head; let mut fast = &head; while fast.is_some() && fast.as_ref().unwrap().next.is_some() { slow = &slow.as_ref().unwrap().next; fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next; } return slow.clone(); } } |
Pythonのコードと比較しながら見ると、ほんの少しだけわかるような気がする。
time:1ms
space :2mb
補足・参考・感想
参考 ※以下の2サイトはとてもわかりやすかった
↓ListNodeの中身とLeetcodeでの連結リストのinputについて
LeetCodeの入出力値の型に騙されるな – 206. Reverse Linked List – Qiita
↓LeetCodeでの連結リストの問題パターン
連結リストの扱いに慣れなくて難しい。連結リストをListNodeで扱うのはLeetCodeに特有なのか一般的なのか調べてみた方が良いかもしれない。
しばらくは連結リストの問題を集中的に解いてみる。
コメント