質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
参照

参照は、プログラミングにおいて変数や関数といったメモリ空間上での所在を指示するデータのことを指します。その中にはデータ自体は含まれず、他の場所にある情報を間接的に指示するプログラムです。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

連結リスト

連結リストとは、データ構造のひとつであるリストの中で、要素が前後の要素の情報を持つことで、要素が連結(リンク)しているリストの事を呼びます。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

3回答

1556閲覧

Linked Listのコードが解読が出来ない

mns

総合スコア3

参照

参照は、プログラミングにおいて変数や関数といったメモリ空間上での所在を指示するデータのことを指します。その中にはデータ自体は含まれず、他の場所にある情報を間接的に指示するプログラムです。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

連結リスト

連結リストとは、データ構造のひとつであるリストの中で、要素が前後の要素の情報を持つことで、要素が連結(リンク)しているリストの事を呼びます。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2021/04/24 07:14

leetcodeの「206. Reverse Linked List」問題について

回答がわからず検索したところ下記のコードに行き着きましたが、解読できず困っています。
※LinkedListというよりpythonの仕様理解不足の気はしていますが

最初のwhile文はheadをstackに格納するため(後からpop()で逆順取得するため)というのは
理解できましたが、後半のwhile文でcurとstackの操作しか行われておらず、なぜheadの値が書き変わっているのか?(どこで参照が渡っている?)がわからずつまづいています。

実装したい仕様
inputしたListNode型を逆順にして返す
(ex.) Input: head = [1,2,3,4,5]  Output: [5,4,3,2,1]

python

1# Definition for singly-linked list. 2# class ListNode: 3# def __init__(self, val=0, next=None): 4# self.val = val 5# self.next = next 6class Solution: 7 def reverseList(self, head: ListNode) -> ListNode: 8 if not head: 9 return None 10 11 stack = [] 12 13 while head.next: 14 stack.append(head) 15 head = head.next 16 17 while stack: 18 cur = stack.pop() 19 cur.next.next = cur 20 cur.next = None 21 22 return head

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

ppaul

2021/04/24 10:01

再帰関数を使えば5行で書けて、ずっとわかりやすいですね。 こういう出来の悪い解法でも読めないのは困りますが、もっと良い解法を探しましょう。
guest

回答3

0

ベストアンサー

絵にかいて動作を1つずつ確認してみることをお勧めします。
code を説明していくと
while head.next: 終了後 head は、最後の ListNode です。
while stack: の最初の cur = stack.pop() で cur に最後の1つ前の ListNode を持って来ています。
cur.next は最後の ListNode(つまり現在の head )ですので
cur.next.next = cur で head.next に最後の1つ前の ListNode を入れています。
cur.next = None で最後の1つ前の ListNode の next を None にしています。
これで、逆順並び替えの最初の接続が完了ですね。

個人的には、保守性の悪い code に思えます。
すべて stack に保存して繋ぎ直す次のような code がわかりやすいでしょう。

Python

1 while head: 2 stack.append(head) 3 head = head.next 4 5 cur = head = stack.pop() 6 while stack: 7 cur.next = stack.pop() 8 cur = cur.next 9 cur.next = None

一旦、最後の ListNode を stack に積んでからすぐ pop する無駄が気になるのであれば、最後の ListNode は stack に積まずに次のようにした方が1行増えてもわかりやすいでしょうね。

Python

1 while head.next: 2 stack.append(head) 3 head = head.next 4 5 cur = head 6 while stack: 7 cur.next = stack.pop() 8 cur = cur.next 9 cur.next = None

参考に再帰を使ったコードも提示しておきます。

Python

1 def reverseList(self, head: ListNode) -> ListNode: 2 if not head: 3 return None 4 self.head = head 5 if head.next: 6 self.reverseList(head.next) 7 head.next.next = head 8 head.next = None 9 return self.head

再帰より stack 使わず単純に while で繋ぎ直す方が簡単ですね。こちらも参考に提示しておきます。
Python の代入文は複数代入が可能で右辺を先に評価するため繋ぎ直し処理を4行で実装できます。

Python

1 def reverseList(self, head: ListNode) -> ListNode: 2 pre, cur = None, head 3 while cur: 4 cur.next, pre, cur = pre, cur, cur.next 5 return pre

投稿2021/04/24 12:12

編集2021/04/24 22:33
lehshell

総合スコア1147

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

mns

2021/04/25 11:23

>絵にかいて動作を1つずつ確認 これでやっと理解できました。 連結リストはじめ、アルゴリズムの知見が無いのに、python不慣れで参考コードの品質も確認出来ず。。。 (メインJavaですがleetCodeではpython推奨と聞いて練習中) 他の方も丁寧に回答いただきましたが、改善コードと再起法についてもご丁寧にありがとうございます。
guest

0

pythonの変数は参照渡しなので元のListNodeとstackに入れたListNodeとcurに取り出したListNodeは全く同じものを指します。
どれかを編集したら他で参照してる同じListNode全てが書き変わる訳です。

例えば

py

1a = [['foo', 'bar'], [1, 2]] 2b = a[0] 3b[0] = 'hoge' 4 5print(a) #-> [['hoge', 'bar'], [1, 2]]

となります。

投稿2021/04/24 09:36

kairi003

総合スコア1330

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

1つめのwhileの中でheadを残りの先頭に貼り替えていますよね。ということは、whileを回りきった後では、headはリストの最後のものを保持しています。stackの先頭に入っているのも同じものです。

2つめのwhileでstackの中身を順に(結果としてもととは逆順に)つないでいますが、headは書き換えていないので、想定どおり、逆順になったリストの先頭を指していることになります。

投稿2021/04/24 07:51

TakaiY

総合スコア12666

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問