5일 - 정렬된 목록 II에서 중복 항목 제거

문제

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

예 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

예 2:

Input: head = [1,1,1,2,3]
Output: [2,3]

Constraints:

• The number of nodes in the list is in the range [0, 300].
• -100 <= Node.val <= 100 The list is guaranteed to be sorted in ascending order.

내 테스트

import pytest
from typing import List
from .util import ListNode, toListNode, toList
from .Day5 import Solution

s = Solution()


@pytest.mark.parametrize(
    "input,expected",
    [
        ([1, 2, 3, 3, 4, 4, 5], [1, 2, 5]),
        ([1, 2, 3, 3, 3, 4, 4, 5], [1, 2, 5]),
        ([1, 1, 1, 2, 3], [2, 3]),
        ([2, 3, 4], [2, 3, 4]),
        ([1, 1], []),
        ([0], [0]),
        ([], []),
        ([1, 1, 2, 2], []),
    ],
)
def test_remove_duplicates(input, expected):
    assert toList(s.deleteDuplicates(toListNode(input))) == expected

내 솔루션

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        holder = ListNode(0, head)
        dummy_head = holder
        next_node = head

        while next_node:
            if next_node.next is not None and next_node.next.val == next_node.val:
                while (
                    next_node.next is not None and next_node.val == next_node.next.val
                ):
                    next_node = next_node.next
                dummy_head.next = next_node.next
            else:
                dummy_head = dummy_head.next
            next_node = next_node.next

        return holder.next

분석

내 해설

이것은 매우 쉬울 것이라고 생각했지만 포인터를 알아 내려고 여러 번 혼란스러워했습니다. 나는 질문을 올바르게 읽지 않았고 일치하는 숫자의 모든 인스턴스를 제거하지 않고 중복을 제거해야 한다고 생각했기 때문에 첫 번째 시도를 망쳤습니다.

처음에는 현재 헤드와 다음 목록 항목에 대한 포인터를 유지해야 한다고 생각했습니다. 일치하는 항목이 있는 동안 내가 해야 할 일은 next 포인터를 증가시키는 것이라고 가정했습니다. 일치하는 항목이 없으면 head.next를 next로 범프합니다. 물론 계속하려면 head.next에 대한 또 다른 포인터가 필요합니다. 나는 많은 if 문과 엉망인 코드로 끝났습니다.

가장 쉬운 일은 holder를 쉽게 증가시킬 수 있는 head 포인터를 만드는 것임을 깨닫는 데 시간이 걸렸습니다(처음에 중복 항목이 있는 경우). 그런 다음 더미 헤드 포인터도 설정할 수 있습니다. next_node 포인터로.

그런 다음 중복을 확인하고 모든 중복에 대해 next_node 포인터를 증가시킵니다. 그런 다음 원래 머리를 dummy_head에 보관했기 때문에 안전하게 할 수 있는 복제를 지나서 holder 포인터를 밀어 넣습니다.

중복이 표시되지 않으면 다음 노드에 대한 포인터dummy_head를 증가시킵니다.
목록.

어제 인터뷰에서 이런 말을 들었다면 지금은 해결책이 너무 뻔한데도 난감했을 것 같다.