オットセイの経営日誌

データサイエンス系ベンチャーを経営してます。経営のこと、趣味のことつぶやきます。

LeetCode / Remove Duplicates from Sorted List

https://leetcode.com/problems/remove-duplicates-from-sorted-list/

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:
Input: 1->1->2
Output: 1->2

Example 2:
Input: 1->1->2->3->3
Output: 1->2->3

LeetCode頻出のLinkedListの問題。以前の記事にも登場してます。

今回の記事も長くはないですが、裏には数多の苦悩の道のりがありました。
LinkedListの性質(より正確には、Pythonの変数間の参照)がどうにも理解できず、youtubeでインドの方の解説動画とかを読み漁りました。

解答・解説

解法1

公式のJavaの解答をPythonに翻訳したのが以下です(余談ですが、LeetCodeをやってると高級言語から入った人でもC++とかJavaが段々読めるようになってくるのがおトクですね)。

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        # currentとheadの間で参照を渡して、headの各nodeをcurrentを動かしながら移動し、重複nodeを発見・削除する
        current = head
        while current and current.next:
            # 重複nodeを発見したら、重複nodeの次のnodeにcurrent.nextをポイントさせて、重複nodeを削除する
            if current.next.val == current.val:
                current.next = current.next.next
            # 重複nodeでなかったら、通常のiterationを進める(currentを次のnodeにポイントさせる)
            else:
                current = current.next
        return head

、、、ということなんですが、皆さん分かりますか?
私はさっぱり分かりませんでした。current.next = current.next.nextだとnodeは削除されるのに、current = current.nextだとnodeは削除されないのはなぜ?

どうにも困ったので、慣れ親しんだデータ型であるlistで同様の状況を再現してみて、改めて考えてみました。

head = [1,1,2]
current = head
while current and current[1:]:
    if current[1] == current[0]:
        current[1:] = current[2:]
    else:
        current = current[1:]
    print('current:{}'.format(current), 'head:{}'.format(head))
head
# ---> current:[1, 2] head:[1, 2]
# ---> current:[2] head:[1, 2]
# ---> [1, 2]

分かりやすいように、print文でIterationの途中のcurrent, headの値を吐き出すようにしました。
この結果から、朧げながら私の理解は、
current[1:] = current[2:]ではcurrentとheadの間の参照は保持したまま値が代入されている(のでheadの値も変わる)が、
current = current[1:]では参照自体が1つ先に移動する(のでheadの値が変わるわけではない)、
ということかと思いました。

間違っていたら是非是非ご指摘ください。