3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

LeetCode / Remove Duplicates from Sorted List

Posted at

ブログ記事からの転載)

[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の値が変わるわけではない)、
ということかと思いました。

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

3
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?