2.1 Remove Dups

Created: September 1, 2021 11:03 PM Tags: duplicate, linkedlist

2.2 Remove Dups: 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?

• Answer) In order to remove dulpicates from a linked list, I need to be able to track duplicates. A set data structure will work well here. I iterate through the linked list, adding each element to a set. When I discover a duplicate element, I remove the element and continue iterating.

  If we don’t have a buffer, we can iterate with two pointers: current which iterates through the linked list, and runner which checks all subsequent nodes for duplicates.

• 답변) Set 자료형을 이용하여 중복값을 제거할 수 있다. 리스트를 처음부터 끝까지 반복하면서 데이터를 Set 자료형에 추가하고 다음 리스트의 요소 중 이미 Set에 있는 자료는 중복 자료이므로 제거해나갈 수 있다. 이를 구현하면 아래와 같다. 아래의 경우, O(N) time(where N is the number of elements in the linked list) 과 O(N) space를 가진다. 중복값이 없는 경우 Set에는 최대 N개만큼 계속 채워질 수 있다.

    # L1 : 5 > 6 > (5 >) 3
    #                    *
    # set : {5, 6, 3}
  
    def deleteDups(L1 : SList):
        t = L1.head
        s1 = set()
        pre = None
        while t != None:
            if t.data in s1:
                pre.next = t.next
            else:
                s1.add(t.data)
                pre = t
            t = t.next
  

  만약, 추가적인 버퍼가 주어지지 않는다면 우리는 링크드 리스트만으로 O(1) Space로 문제를 풀어야한다. 이 경우 두 개의 포인터를 이용하여 해결할 수 있다. 예를들어, 리스트의 첫 번쨰 노드부터 시작하여 첫 노드와 뒤 모든 노드를 비교하여 첫 노드와 같은 노드는 제거한다. 그리고 두번째 노드와 또 뒤의 모든 노드를 비교하여 같은 노드는 제거한다. 이와 같은 과정을 마지막 노드까지 수행하면 O(n^2) time이지만, 추가적인 공간을 사용하지 않고 문제를 해결할 수 있다.

    # L1 : 5 > 6 > (5 >) 3
    #      *
    # cur / runner
    #  5  / 6 > [5 >] 3
    #  6  / 3
  
    def deleteDupsNoBuffer(L1 : SList):
        cur = L1.head
        while cur.next != None:
            runner = cur
            while runner.next != None:
                if runner.next.data == cur.data:
                    runner.next = runner.next.next
                else:
                    runner = runner.next
            cur = cur.next
  

  아래는 테스트를 위한 전체 코드이다.

    class Node(object):
        def __init__(self, data, next = None):
            self.data = data
            self.next = next
  
    class SList(object):
        def __init__(self):
            self.head = Node(None)
            self.size = 0
        def is_empty(self):
            return False if self.size > 0  else True
        def appendleft(data):
            if self.is_empty():
                self.head = Node(data)
            else:
                self.head = self.Node(data, self.head)
            self.size += 1
        def append(self, data):
            if self.is_empty():
                self.head = Node(data)
            else:
                target = self.head
                while target.next != None:
                    target = target.next
                target.next = Node(data)
            self.size += 1
  
    def deleteDups(L1 : SList):
        t = L1.head
        s1 = set()
        pre = None
        while t != None:
            if t.data in s1:
                pre.next = t.next
            else:
                s1.add(t.data)
                pre = t
            t = t.next
        print(s1)
  
    def deleteDupsNoBuffer(L1 : SList):
        cur = L1.head
        while cur.next != None:
            runner = cur
            while runner.next != None:
                if runner.next.data == cur.data:
                    runner.next = runner.next.next
                else:
                    runner = runner.next
            cur = cur.next
  
    L1 = SList()
    L1.append(5)
    L1.append(3)
    L1.append(5)
    L1.append(6)
    L1.append(3)
  
    print("before delete Dups##################")
    t = L1.head
    i = 0
    while t!=None:
        print("i : " +str(i) )
        print(t.data)
        t = t.next
        i += 1
    print("#####################################")
    #deleteDups(L1)
    deleteDupsNoBuffer(L1)
    print("#####################################")
    print("after delete Dups##################")
    t = L1.head
    i = 0
    while t!=None:
        print("i : " +str(i) )
        print(t.data)
        t = t.next
        i += 1