LeetCode Problems解いた：19. Remove Nth Node From End of List

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

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

例)リストノード：[1,2,3,4,5]、n=2の場合
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/85457/f4573b17-015b-89e5-2dd5-6e47f77a3ffb.png)

## コード
<details>
<summary>コード全容</summary>

```python: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)
```
</details>

## 考え方
再帰処理を使う(`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!"から拝借)
<details>
<summary>one passでない解法</summary>

```python: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
```
</details>
<details>
<summary>ちゃんとしたone pass</summary>

```python: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
```
</details>

---
そもそもなぜ上記の解にたどり着いたかというと、最初に実現したかった「one passでない」解がうまく動かなかったためである。実現しようとした際に、以下の部分で躓いた。

```python:
tmp = tmp.next
tmp.next = tmp.next.next
```
両者ともnをずらせば本質的には同じ意味になるはずであるが、ノード削除で機能するのは下の記述のみ。しかも、2処理目-2のループ部で上記も使用する。今更だが何が違うのか。

―簡単に言うと、上が「tmpの再定義」、下が「tmpの要素の変更」となる。
* 再定義の場合は、それをそのオブジェクトを参照する変数とのリンクが切れる。
```python
a = [1,2,3]
b = a
a = [4,5,6]
# この場合、bは[1,2,3]、aは[4,5,6]となる。aの指し示すところのみ変わる。
```
* 要素の変更の場合は、当然、参照するオブジェクトとのリンクは切れない。
```python
a = [1,2,3]
b = a
a[0] = 4
#この場合、a = b = [4,2,3]となる。
```
つまり、ループ部ではtmpが再定義しなおされているので、参照元のheadには影響が出ておらず、最後の`tmp.next = tmp.next.next`のみ「要素の変更」となり、tmpの参照元であるheadの要素に影響が出ている。
変数に値が代入されている、と考えるよりは **変数を定義=値が格納されている番地が変数にメモされる** 、というイメージ。
代入、参照が入り混じる際は気を付けよう。

参考サイト)
[Python♪「参照渡し後の要素の変更」と「参照渡し後の再定義」の違い](https://snowtree-injune.com/2018/07/28/post-688/)