LeetCodeの問題集、19. Remove Nth Node From End of Listがacceptされたので、備忘録として。

概要

リストノードの、後ろからn番目のノードを取り除く、という問題。
前から数えて 、ではないのが難しい。

例)リストノード：[1,2,3,4,5]、n=2の場合

コード

コード全容

Solution

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でない解法

Solution - not "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

Solution - genuine "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の要素に影響が出ている。
変数に値が代入されている、と考えるよりは 変数を定義=値が格納されている番地が変数にメモされる 、というイメージ。
代入、参照が入り混じる際は気を付けよう。

参考サイト)
Python♪「参照渡し後の要素の変更」と「参照渡し後の再定義」の違い