(ブログ記事からの転載)
[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の値が変わるわけではない)、
ということかと思いました。
間違っていたら是非是非ご指摘ください。