📌 출처

엔지니어 대한민국
https://www.youtube.com/watch?v=Ce4baygLMz0

📌 두가지 방법

🔥 Set 이용

node.next의 값이 set에 있을 경우, node.next = node.next.next 로 바꾸어준다.

값이 없을 시, node를 다음 값으로 이동하고, 해당 node의 값을 set에 넣어준다.

🔥 코드

class Node:
    def __init__(self,val):
        self.val = val
        self.next = None

    def add(self,val):
        node = self
        while node.next is not None:
            node=node.next
        node.next = Node(val)
    def print(self):
        node = self
        while node:
            print(node.val)
            node=node.next

    def remove_duplicate(self):
        hash_set = set()
        node = self
        hash_set.add(node.val)
        while node is not None and node.next is not None:
            if node.next.val in hash_set:
                node.next = node.next.next
            else:
                node=node.next
                hash_set.add(node.val)


n1 = Node(1)
n1.add(2)
n1.add(3)
n1.add(3)
n1.add(4)
n1.add(4)
n1.add(4)
n1.add(4)
n1.add(5)

n1.remove_duplicate()
n1.print()

🤡 복잡도

시간복잡도 O(n)
공간복잡도 O(n)

🔥 러너 이용

따로 버퍼공간 ( 위의 예에서 set )을 이용하지 말고 풀어보라.

해당 node를 순회하면서, 해당 node에 해당하는 runner를 둔다.

위 그림과 같이 node는 고정하면서, runner는 앞으로 나아가며, node.val == runner.next.val 검사를 한다.

위의 경우 해당하므로

runner.next = runner.next.next로 만들어주고, runner를 전진시킨다.

🔥 코드

class Node:
    def __init__(self,val):
        self.val = val
        self.next = None

    def add(self,val):
        node = self
        while node.next is not None:
            node=node.next
        node.next = Node(val)
    def print(self):
        node = self
        while node:
            print(node.val)
            node=node.next

    def remove_duplicate(self):
        node = self
        while node is not None and node.next is not None:
            runner = node
            while runner.next is not None :
                if node.val == runner.next.val:
                    runner.next =runner.next.next
                else:
                    runner=runner.next
            node=node.next

n1 = Node(1)
n1.add(2)
n1.add(3)
n1.add(3)
n1.add(4)
n1.add(4)
n1.add(4)
n1.add(4)
n1.add(5)

n1.remove_duplicate()
n1.print()

🤡 복잡도

시간복잡도는 O(n^2) 이지만
공간복잡도는 O(1) 이다.