$K$th to Last in Linked List

# 問題

片連結リストの，後ろからk番目の要素を見つける．

1
2
3
4
class LinkedListNode:
    def __init__(self, data, next_node):
        self.data = data
        self.next_node = next_node

# 答え

片連結リストの長さLが与えられるなら，前からL-k番目を取ればいい．

片連結リストの長さが与えられないときはチョット工夫する．

再帰で書く

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def find_kth_to_last(node, k):
    # base case
    if node is None:
        return 0

    idx = find_kth_to_last(node.next_node, k) + 1

    if idx == k:
        print("{}th to last: {}".format(idx, node.data))

    return idx

ポインタ 2 つ用意する．ポインタ同士がk離れているようにしておくことで時間計算量$O(n)$，空間計算量$O(1)$で済む．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def find_kth_to_last(head, k):
    pointer0 = head
    pointer1 = head
    for _ in range(k):
        pointer0 = pointer0.next_node

    while pointer0 is not None:
        pointer0 = pointer0.next_node
        pointer1 = pointer1.next_node

    print("{}th to last: {}".format(k, pointer1.data))