알고리즘 with python.03

링크드 리스트 끝에서 k 번째 값 출력하기

링크드 리스트 중 원하는 위치의 값을 출력하는 코드입니다.

1번째 코드

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


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def get_kth_node_from_last(self, k):
        length = 1
        cur = self.head

        while cur.next is not None:
            cur = cur.next
            length += 1
        end_length = length - k
        cur = self.head
        for i in range(end_length):
            cur = cur.next
        return cur


linked_list = LinkedList(6)
linked_list.append(7)
linked_list.append(8)

print()
print(linked_list.get_kth_node_from_last(2).data)

위 코드는
1. LinkedList 길이 전부 알아내기
2. 그 길이에서 K 만큼 뺀 길이만큼 이동

아래의 코드는
1. 노드를 두개 잡는다.
2. 한 노드를 다른 노드보다 K 만큼 떨어지게 한다.
3. 그리고 계속 한 칸씩 같이 이동한다.
4. 만약 더 빨ㄴ 노드가 끝에 도달했다면 느린 노드는 끝에서
   K만큼 떨어진 노드가 되므로 바로 반환한다.

바뀌는 코드

    def get_kth_node_from_last(self, k):
        last = self.head
        fast = self.head

        for i in range(k):
            fast = fast.next

        while fast is not None:
            fast = fast.next
            last = last.next

        return last

2번째 코드

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


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def get_kth_node_from_last(self, k):
        last = self.head
        fast = self.head

        for i in range(k):
            fast = fast.next

        while fast is not None:
            fast = fast.next
            last = last.next

        return last


linked_list = LinkedList(6)
linked_list.append(7)
linked_list.append(8)

print()
print(linked_list.get_kth_node_from_last(2).data)

시간 복잡도의 변화

위 코드는
1. LinkedList 길이 전부 알아내기 O(N)
2. 그 길이에서 K 만큼 뺀 길이만큼 이동 O(N-K)

아래의 코드는
1. 노드를 두개 잡는다.
2. 한 노드를 다른 노드보다 K 만큼 떨어지게 한다.
3. 그리고 계속 한 칸씩 같이 이동한다.
4. 만약 더 빨ㄴ 노드가 끝에 도달했다면 느린 노드는 끝에서
   K만큼 떨어진 노드가 되므로 바로 반환한다.  O(N)  O(N-K)

코드는 이해하기 쉽게 간소화 됬지만 시간복잡도의 변화는 없다.