Ch02 LinkedList

Ch02 LinkedList

---

2.1 정렬되지 않은 linkedList에서 중복된 값을 삭제하는 코드를 작성 한다.

해법1
set자료 구조에 하나씩 저장하면서 순회하는 방식을 사용한다.
단 한번의 순회로 모두 처리 할 수 있다.
복잡도는 O(n)이다.

def remove_dups(ll):
    if ll.head is None:
        return

    current = ll.head
    seen = set([current.value])
    while current.next:
        if current.next.value in seen:
            current.next = current.next.next
        else:
            seen.add(current.next.value)
            current = current.next

    return ll

실행결과

# 제거 전
1 -> 6 -> 1 -> 4 -> 3 -> 2 -> 4 -> 2 -> 2 -> 5 -> 5 -> 4 -> 2 -> 3 -> 8 -> 6 -> 2 -> 0 -> 1 -> 6 -> 3 -> 6 -> 2 -> 2 -> 6 -> 2 -> 1 -> 6 -> 2 -> 4 -> 2 -> 4 -> 7 -> 8 -> 4 -> 4 -> 3 -> 8 -> 5 -> 5 -> 0 -> 7 -> 7 -> 4 -> 1 -> 1 -> 1 -> 8 -> 5 -> 0 -> 7 -> 5 -> 9 -> 3 -> 0 -> 9 -> 2 -> 0 -> 4 -> 0 -> 0 -> 3 -> 1 -> 3 -> 5 -> 1 -> 0 -> 0 -> 5 -> 9 -> 7 -> 7 -> 0 -> 3 -> 3 -> 1 -> 7 -> 5 -> 5 -> 9 -> 7 -> 4 -> 2 -> 4 -> 6 -> 5 -> 3 -> 2 -> 9 -> 9 -> 8 -> 5 -> 1 -> 7 -> 4 -> 1 -> 8 -> 4 -> 3 -> 9

# 제거 후
1 -> 6 -> 4 -> 3 -> 2 -> 5 -> 8 -> 0 -> 7 -> 9

제약사항

• temporary buffer를 허용하지 않는다.

해법
버퍼를 사용할 수 없다면 두 개의 포인터를 사용해 순회하여 문제를 해결할 수 있다. current라는 포인터로는 연결 리스트를 순회하고, runner로는 그 뒤에 중복이 있는지 확인 하는 것이다.

하지만 하나의 current node에 대해서 반복을 수행을 계속 해야 하므로 공간 복잡도는 O(1)이 되지만, 시간 복잡도는 O(N^2)이 된다.

def remove_dups_followup(ll):
    if ll.head is None:
        return

    current = ll.head
    while current:
        runner = current
        while runner.next:
            if runner.next.value == current.value:
                runner.next = runner.next.next
            else:
                runner = runner.next
        current = current.next

    return ll.head

실행결과

# 제거 전
1 -> 7 -> 8 -> 1 -> 5 -> 7 -> 8 -> 4 -> 9 -> 6 -> 5 -> 9 -> 0 -> 3 -> 8 -> 8 -> 9 -> 3 -> 2 -> 8 -> 7 -> 6 -> 7 -> 9 -> 9 -> 8 -> 5 -> 8 -> 9 -> 5 -> 1 -> 2 -> 6 -> 5 -> 6 -> 9 -> 2 -> 9 -> 2 -> 4 -> 4 -> 0 -> 8 -> 1 -> 5 -> 9 -> 9 -> 5 -> 0 -> 2 -> 9 -> 8 -> 0 -> 6 -> 1 -> 2 -> 1 -> 3 -> 0 -> 7 -> 6 -> 8 -> 1 -> 4 -> 5 -> 0 -> 2 -> 4 -> 9 -> 9 -> 9 -> 5 -> 3 -> 8 -> 0 -> 5 -> 7 -> 2 -> 8 -> 0 -> 3 -> 2 -> 8 -> 0 -> 0 -> 8 -> 2 -> 9 -> 0 -> 5 -> 3 -> 6 -> 8 -> 2 -> 1 -> 7 -> 8 -> 3 -> 7 -> 6

# 제거 후
1 -> 7 -> 8 -> 5 -> 4 -> 9 -> 6 -> 0 -> 3 -> 2

2.2 단방향 Linked List에서 k번째 요소를 찾는 코드를 구현 해야 한다.

해법1
재귀함수를 이용하는 방법

순회하고 매번 index를 저장하기 때문에 O(n)의 복잡도를 가지게 된다. 해당 위치에서 값을 출력하고 index는 return하는 방법으로 구현 했다.

def recursive_kth_to_last(ll, k):
    if ll is None:
        return 0
    i = recursive_kth_to_last(ll.next, k) + 1

    if i is k:
        print(ll.value)
    return i

실행결과

# 생성된 linked list
71 -> 83 -> 3 -> 2 -> 59 -> 25 -> 33 -> 40 -> 21 -> 93

# 뒤에서 3번 째 index라고 하면
40 # 값

해법2
순환적(iterarive) 방법으로 해결할 수 있다.
직관적이지는 않지만 좀 더 최적인 방법은, 순환적으로 푸는 것이다. 두 개의 포인터 p1과 p2를 사용한다. p1이 리스트 시작 노드를 가리키게 한 다음, p2를 k 노드만큼 움직여서 p1과 p2가 k 노드만큼 떨어져 있도록 만든다. 그런 다음, p1과 p2를 보조를 맞춰 같이 이동시킨다. p2는 LENGTH-k번 후에 연결 리스트의 맨 마지막 노드에 도달할 것이다. 바로 그 시점에, p1은 LENGTH-k번 노드, 그러니까 뒤에서부터 k번째 노드를 가리키게 된다.

코드

def kth_to_last(ll, k):
    runner = current = ll.head
    for i in range(k):
        if runner is None:
            return None
        runner = runner.next

    while runner:
        current = current.next
        runner = runner.next

    return current

실행결과

11 -> 11 -> 83 -> 92 -> 74 -> 2 -> 80 -> 97 -> 76 -> 88
97

2.3 Delete Middle Node

중간 노드를 삭제하는 알고리즘을 구현 한다. 즉 head나 tail을 제외한 아무 노드나 삭제 할 수 있어야 한다.

그렇다고 정확히 middle일 필요도 없다.

example
input: the node c from the linked list a->b->c->d->e->f
result: nothing is returned, but the new linked list looks like a->b->d->e->f

python에서는 쉽게 구현이 가능하다.

def delete_middle_node(node):
    node.value = node.next.value
    node.next = node.next.next

ll = LinkedList()
ll.add_multiple([1, 2, 3, 4])
middle_node = ll.add(5)
ll.add_multiple([7, 8, 9])

print(ll)
delete_middle_node(middle_node)
print(ll)

실행결과

1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 8 -> 9
1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 9

2.4 x값을 갖는 노드를 기준으로 연결 리스트를 나누는 코드를 작성하라. x 보다 작은 값을 갖는 노드가 x와 같거나 더 큰 값을 갖는 노드들보다 앞쪽에 오도록 하면 된다.

연결리스트를 사용하면 쉽게 해결 된다.
x를 기준으로 작은 값을 저장하는 것과 그렇지 않은것을 저장 하는 것으로 나누면 된다.

index를 1개만 이용해서 앞에서 부터 채우게 하면 좀 더 메모리를 절약할 수 있다.

def partition(ll, x):
    current = ll.tail = ll.head

    while current:
        nextNode = current.next
        current.next = None
        if current.value < x:
            current.next = ll.head
            ll.head = current
        else:
            ll.tail.next = current
            ll.tail = current
        current = nextNode
        
    # Error check in case all nodes are less than x
    if ll.tail.next is not None:
        ll.tail.next = None


ll = LinkedList()
ll.generate(10, 0, 99)
print(ll)
partition(ll, ll.head.value)
print(ll)

실행결과
partition은 46으로 선택했을 때의 결과이다.

46 -> 53 -> 52 -> 69 -> 48 -> 3 -> 23 -> 59 -> 2 -> 91
2 -> 23 -> 3 -> 46 -> 53 -> 52 -> 69 -> 48 -> 59 -> 91

2.5 Sum Lists

• 2개의 연결 리스트가 있고 각각은 싱글 digit을 포함하고 있다. 그리고 이 숫자는 역순으로 정렬되어 있다. 즉 1의 자리숫자가 맨 앞에 있다는 뜻이 된다. 이 두개의 연결 리스트를 더해서 그 결과를 반환하는 코드를 작성하라.

Example
Input: (7->1->6) + (5->9->2). That is, 617 + 295
Output: 2->1->9. That is 912.

코드

def sum_lists(ll_a, ll_b):
    n1, n2 = ll_a.head, ll_b.head
    ll = LinkedList()
    carry = 0
    while n1 or n2:
        result = carry
        if n1:
            result += n1.value
            n1 = n1.next
        if n2:
            result += n2.value
            n2 = n2.next

        ll.add(result % 10)
        carry = result // 10

    if carry:
        ll.add(carry)

    return ll

실행 결과

5 -> 3 -> 7 -> 7
8 -> 6 -> 8
3 -> 0 -> 6 -> 8

Follow up problem

• 길이가 맞지 않는 경우
• 계산결과를 head에 붙여서 처리하는 방식으로 구현

코드

def sum_lists_followup(ll_a, ll_b):
    # Pad the shorter list with zeros
    if len(ll_a) < len(ll_b):
        for i in range(len(ll_b) - len(ll_a)):
            ll_a.add_to_beginning(0)
    else:
        for i in range(len(ll_a) - len(ll_b)):
            ll_b.add_to_beginning(0)

    # Find sum
    n1, n2 = ll_a.head, ll_b.head
    result = 0
    while n1 and n2:
        result = (result * 10) + n1.value + n2.value
        n1 = n1.next
        n2 = n2.next

    # Create new linked list
    ll = LinkedList()
    ll.add_multiple([int(i) for i in str(result)])

    return ll

실행결과

뒤에서 부터 1의 자리로 생각 하기 때문에 결과가 다르다.

5 -> 3 -> 7 -> 7
8 -> 6 -> 8
6 -> 2 -> 4 -> 5

2.6 주어진 연결 리스트가 회문(palindrome)인지 검사하는 함수를 작성하라

palindrome이라 함은 앞에서 보다 뒤에서 보다 같은 구조를 뜻한다.
예
0->1->2->1->0

해법1: 뒤집어 비교한다.

• 포인트는 절반만 비교한다는 것이다.

해법2: 순환적(iterative) 접근법

• 리스트 앞 절반을 뒤집는 것을 스택을 사용해서 구현 한다.
• 연결리스트의 길이를 알 경우 절반만 push 하면 된다 (홀수인 경우에도 올바르게 처리 해줘야 한다).
• 길이를 모를 경우 fast runner와 slow runner를 적절히 조합해서 사용 한다.

해법3: 재귀적 접근법

코드

def is_palindrome(ll):
    fast = slow = ll.head
    stack = []

    while fast and fast.next:
        stack.append(slow.value)
        slow = slow.next
        fast = fast.next.next

    if fast:
        slow = slow.next

    while slow:
        top = stack.pop()

        if top != slow.value:
            return False

        slow = slow.next

    return True


ll_true = LinkedList([1, 2, 3, 4, 5, 4, 3, 2, 1])
print(is_palindrome(ll_true))
ll_false = LinkedList([1, 2, 3, 4, 5, 6, 7, 8, 9])
print(is_palindrome(ll_false))

실행 결과

True
False