[알고리즘] 연결리스트 안에서 중복 없애기, 뒤에서 k번째 요소 찾기

1. 정렬되어 있지 않은 연결리스트에서 중복되는 원소를 제거하기

 

# 연결리스트를 순회하면서 딕셔너리에 Node의 data를 담아두고
# data 값의 key가 존재하면 노드를 삭제
def remove_duplication1(node):
    compare_table = {}
    previous = None

    while node:
        if node.data in compare_table:
            previous.next = node.next
        else:
            compare_table[node.data] = 1

        previous = node
        node = node.next

 

# 다른 자료구조를 사용할 수 없는 경우 연결리스트 내에서 두개의 포인터를 사용해서
# 중복되는 원소가 있는지 확인
def remove_duplication2(head):
    cur = head

    while cur:
        runner = cur

        while runner.next:
            if cur.data == runner.next.data:
            	# 중복되는 데이터가 발견된다면
                # 이전 노드의 next에 다음 노드를 연결
                runner.next = runner.next.next
            else:
            	# 중복값이 아니라면 runner를 다음 노드로 이동
                runner = runner.next

        cur = cur.next

 

 

 

2. 뒤에서 k번째 요소 찾기

 

# 재귀적 방법
def find_element_recursive(k, node):
    if not node:
        return [0, None]

    # 연결리스트의 끝까지 이동
    count_and_element = find_element_recursive(k, node.next)

    # 뒤에서 몇번째인지 카운트
    count_and_element[0] += 1

    # 찾고자 하는 원소라면 데이터의 값을 할당
    if count_and_element[0] == k:
        count_and_element[1] = node.data
        return count_and_element

    # 찾고자 하는 원소가 아니라면 카운트만 반영한 뒤 리턴
    else:
        return count_and_element

 

 

# 순환적 방법
# 두개의 포인터를 두고 그 중 하나를 k만큼 미리 이동시켜 놓는다면
# 이동시킨 포인터가 연결리스트의 끝에 도착했을 때 나머지 카운터가 끝에서 k번째 위치에 도달하게 된다.
def find_element_iterative(k, head):
    find_element = head
    find_end = head

    for _ in range(k):
        if not find_end:
            return None
        find_end = find_end.next

    while find_end.next:
        find_element = find_element.next
        find_end = find_end.next

    return find_element.data

 

 

Cracking the Coding Interview (Gayle Laakmann McDowell) 의 예제를 파이썬 코드로 작성해 보았습니다.