88706


LeetCodeのアルゴリズム第83問について質問です。

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

以下問題文と入力，出力例です。

> Given the head of a sorted linked list, delete all duplicates such that each
> element appears only once. Return the linked list sorted as well.
>
> 例1
[code]

>     Input: head = [1,1,2]
>     Output: [1,2]
>  
[/code]

>
> 例2
[code]

>     Input: head = [1,1,2,3,3]
>     Output: [1,2,3]
>  
[/code]

下記のコードで正解することはできたのですが，なぜheadの値が更新されるのかわからないです。  
whileループ中にheadの値を出力すると関数deleteDuplicatesが呼び出された直後の値（重複を許した単方向リスト）が出力されますが，whileループを抜けると重複のない単方向リストに変化しています。  
どのような挙動によってこのようなことが起こっているのでしょうか。

[code]

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    
    class Solution:
        def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
            current_node = head
            prev_node = None
            nums = set()
            while current_node:
                if current_node.val not in nums:
                    nums.add(current_node.val)
                    next_node = current_node.next
                    prev_node = current_node
                    current_node = next_node
                    
                elif current_node.val in nums:
                    next_node = current_node.next
                    prev_node.next = next_node
                    current_node = next_node
    
            return head
    
[/code]


CC BY-SA 4.0
2022-05-08T08:29:54.883
88703
2022-05-09T01:28:29.513
2022-05-09T01:28:29.513
3060
52521
question
python アルゴリズム データ構造
Pythonにおける変数の値参照について質問です


SolutionクラスのdeleteDuplicatesメソッドで最初に実行されるのは`current_node = head`です。  
このときcurrent_nodeにはheadの参照が代入されます。

whileループでcurrent_nodeを操作していますが、これはheadを操作しているのと同じです。

`current_node = head`を`head_save = head`に書き換え、  
whileループの中のcurrent_nodeをすべてheadに書き換え、  
headsaveの値でreturnしてもロジックは変わりません。

[code]

    class Solution:
        def deleteDuplicates(self, head):
            head_save = head
            prev_node = None
            nums = set()
            while head:
                if head.val not in nums:
                    nums.add(head.val)
                    next_node = head.next
                    prev_node = head
                    head = next_node
    
                elif head.val in nums:
                    next_node = head.next
                    prev_node.next = next_node
                    head = next_node
    
            return head_save
    
[/code]

このコードは引数headを書き換えていますが、引数の書き換えを勧めている意図はありません。あくまでも説明用のコードです。


CC BY-SA 4.0
2022-05-08T11:16:52.677
88706
2022-05-08T11:16:52.677
35558
88703
answer