[Coding Interview] 링크드 리스트에서 중복된 자료 삭제하기

"""

코딩 인터뷰 문제를 파이썬으로 구현한 글입니다. 

예제 코드에 버그가 있거나 더 나은 방법의 의견교환은 환영입니다.

"""

Write code to remove duplicates from an unsorted linked list. 

FOLLOW UP 

How would you solve this problem if a temporary buffer is not allowed? 

싱글 링크드 리스트에서 중복된 자료를 삭제하는 알고리즘

#노드 생성 클래스
class Node(object):
    def __init__(self, data=None):
        self.data = data
        self.next = None

#링크드 리스트를 set 으로 변환하여 중복값 제거
#O(1) 의 실행 복잡도, BUT 추가 버퍼 필요
def remove_duplicate(node=Node()):
    _tmp_set = set()
    while node:
        _tmp_set.update([node.data])
        node = node.next
    print _tmp_set

#추가 버퍼 필요없음. 단, O(N^2)의 시간 복잡도
def remove_duplicate_no_buffer(node=Node(), head=Node()):
    while node and node.next:
        if node.data is node.next.data:
            if node.next.next:
                node.next = node.next.next
            else:
                node.next = None
            remove_duplicate_no_buffer(head, head)
        node = node.next

#노드 출력
def print_list(node=Node()):
    _tmp_array = list()
    while node:
        _tmp_array.append(node.data)
        node = node.next
    print _tmp_array

#테스트
def test_node():
    node1 = Node(1)
    node2 = Node(1)
    node3 = Node(1)
    node4 = Node(2)
    node5 = Node(2)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5

    remove_duplicate() #if null
    remove_duplicate(node1)
    remove_duplicate_no_buffer(node1, node1)
    print_list(node1)

test_node()