LeetCodeの問題集、19. Remove Nth Node From End of Listがacceptされたので、備忘録として。
概要
リストノードの、後ろからn番目のノードを取り除く、という問題。
前から数えて 、ではないのが難しい。
例)リストノード：[1,2,3,4,5]、n=2の場合
コード
コード全容
def register(node, n, i = 0):
if node.next is None:
i += 1
else:
#こうすることで、お尻のノードからカウントができる
node.next, i = register(node.next, n, i)
i += 1
#該当の場所のみ、registerによりnode.next=node.next.nextとできるので
#指定のノードを削除できる
if i == n:
node = node.next
return (node, i)
class Solution(object):
def removeNthFromEnd(self, head, n):
nl, _ = register(head, n) #再帰中はiが必要だが、最終出力では要らないので捨てている
return(nl)
考え方
再帰処理を使う(node.next, i = register(node.next, n, i))ことで、まずノードリストのお尻に到着してから、カウンターiのカウントを開始することができる。ので、あとは素直にリストのお尻からn番目になった時にnode.next = node.next.nextですよ、としてあげるだけ。
また、i+=1を再帰部の前に持ってくれば、頭から数えることができる。多分。その場合は処理の順番がちょっと変わるので注意。
自分の結果
計算速度：上から数えて約13%のところ(上の方)
メモリ使用量：上から数えて約60%のところ(平均やや下ぐらい)
思ったより早く動作してくれたからOKって感じ。
備考
本設問の最後に「one pass」でできるか？と書いてある。
「one pass」とは「処理にかけるのが1度のみ」というのが主な意味。この設問でいうと、
・1度目のループで場所の特定→2度目のループでその場所を削除する
というのが「one passでない」解法になる。
よく意味が分からず溶き進めていたが、acceptされ、ほかの回答などを見てみると、自分の解法は行き切ってから戻しつつ、という感じの挙動。なので、「半one pass」というのが所感。釣りの時の動きみたいね。
- 「one passでない」解法とちゃんとした「one pass」を以下に載せておく。
(ちゃんとした「one pass」はdiscussの"Short & Simple One-Pass Solution w/ Explanation | Beats 100% | No dummy node required!"から拝借)
one passでない解法
class Solution(object):
def removeNthFromEnd(self, head, n):
count = 0
tmp = head
#ノードリストの長さを調べるループ部(1処理目)
while tmp is not None:
tmp = tmp.next
count += 1
# 頭のノードが指定された場合のみ別処理(2処理目-1)
if n == count: return head.next
tmp = head
#ノードリストの該当部を削除するループ部(2処理目-2)
while count - n > 1:
tmp = tmp.next
count -= 1
tmp.next = tmp.next.next
return head
ちゃんとしたone pass
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
fast = slow = head
for i in range(n):
fast = fast.next
#nodeが一つしかない場合の処理
if not fast: return head.next
#fast-pointerとslow-pointerの追いかけっこ
while fast.next: #fast-pointerがゴールしたところがslowの消したいノードのとこ。
fast, slow = fast.next, slow.next
slow.next = slow.next.next
return head
そもそもなぜ上記の解にたどり着いたかというと、最初に実現したかった「one passでない」解がうまく動かなかったためである。実現しようとした際に、以下の部分で躓いた。
tmp = tmp.next
tmp.next = tmp.next.next
両者ともnをずらせば本質的には同じ意味になるはずであるが、ノード削除で機能するのは下の記述のみ。しかも、2処理目-2のループ部で上記も使用する。今更だが何が違うのか。
―簡単に言うと、上が「tmpの再定義」、下が「tmpの要素の変更」となる。
- 再定義の場合は、それをそのオブジェクトを参照する変数とのリンクが切れる。
a = [1,2,3]
b = a
a = [4,5,6]
# この場合、bは[1,2,3]、aは[4,5,6]となる。aの指し示すところのみ変わる。
- 要素の変更の場合は、当然、参照するオブジェクトとのリンクは切れない。
a = [1,2,3]
b = a
a[0] = 4
#この場合、a = b = [4,2,3]となる。
つまり、ループ部ではtmpが再定義しなおされているので、参照元のheadには影響が出ておらず、最後のtmp.next = tmp.next.nextのみ「要素の変更」となり、tmpの参照元であるheadの要素に影響が出ている。
変数に値が代入されている、と考えるよりは 変数を定義=値が格納されている番地が変数にメモされる 、というイメージ。
代入、参照が入り混じる際は気を付けよう。