Chapter 2: 連結リスト

本章で用いる連結リストについて

単に Python のリストを使うと問題が非常に簡単になってしまう気がしたのでテキストの解説パートにあるように Node クラスを実装した。

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

    def append_to_tail(self, d):
        end = Node(d)
        n = self
        while n.next != None:
            n = n.next
        n.next = end

また、Python のリストから連結リストを作成する make_linked_list 関数、連結リストを表示する print_linked_list 関数も用意した。

def make_linked_list(l):
    head = Node(l[0])
    tail = head
    for i in range(1, len(l)):
        new_node = Node(l[i])
        tail.next = new_node
        new_node.prev = tail
        tail = new_node

    return head

def print_linked_list(node):
    p = node
    while p.next != None:
        print(p.data, end=' ')
        p = p.next
    print(p.data)

これらをまとめて node.py とし、解答のスクリプトではこれを import して使用する。

from node import *

解説

2.1 重複要素の削除

入力例

1 2 3 2 4 5

出力例

1 2 3 4 5

連結リストの先頭から集合 s に要素を入れながら走査する。集合 s 内に要素があればポインタを操作して削除処理を行う。

実装に当たっては、連結リスト末尾の削除処理に注意する。

def delete_dups(linked_list):
    s = set()
    p = linked_list
    while p != None:
        if p.data in s:
            p.prev.next = p.next
            if p.next != None:
                p.next.prev = p.prev
        else:
            s.add(p.data)
        p = p.next

    return linked_list

2.2 後ろから K 番目を返す

入力例

3

1 2 3 4 5 6 7

出力例

5

def print_Kth_to_last(linked_list, k):
    p = linked_list
    length = 0
    while p != None:
        length += 1
        p = p.next

    p = linked_list
    index = length - k
    for _ in range(index):
        p = p.next

    return p.data

2.3 間の要素を削除

保留

2.4 リストの分割

保留（まず問題の意味が分からない）

2.5 リストで表された 2 数の和

入力例

7 1 6

5 9 2

出力例

2 1 9

前半は数値の合計を表す変数（ここでは s）と 10 のべき乗を処理するための変数（counter）を用意して A、B それぞれに対してポインタが None になるまで値を足していけばよい。後半のリスト作成部分はまず None をデータとして持つノードを適当に作ってあげると連結リストを作る際にいい感じに for 文が使える（そして現れる申し訳程度の append_to_tail）。return するのは p.next でよい。

def add_lists(A, B):
    s = 0

    for L in [A, B]:
        counter = 0
        p = L
        while p != None:
            s += p.data * (10 ** counter)
            p = p.next
            counter += 1

    s = str(s)
    p = Node(None)

    for i in range(len(s)):
        p.append_to_tail(int(s[-i-1]))

    return p.next

2.6 回文

入力例

1 2 3 2 1

出力例

True

まず、ポインタを 2 つ用意し、それぞれヘッド・テールを指すようにする。その後はデータを比較しながらポインタ同士を近付けていく。無事中央にたどり着いたら（もしくは p1 と p2 の位置関係が逆転したら）True を返す。

def is_palindrome(L):
    p1 = L
    p2 = L
    while p2.next != None:
        p2 = p2.next

    while (p1 != p2) and (p2.next != p1):
        if p1.data != p2.data:
            return False
        p1 = p1.next
        p2 = p2.prev

    return True

2.7 交わるノード

保留

2.8 ループの検出

保留

感想

ほとんど解けてねーじゃねーか！というか実装がわかんないというか……例えば競技プログラミングって明確に入力と出力が決まっているけどこっちはそういうものがないから非常に戸惑うというか……。あとは解法を見てもピンと来ないものが多いように感じる（これは完全に実力不足）。2.8 とかはポインタをセットに入れていって既存のものがあればループ！とか判定するのはダメなんだろうかとか……。なんというかこう、アルゴリズムというものに対する（悪い方向への）センスのズレを感じる。

Koi なるもの

『世界で闘うプログラミング力を鍛える本』を Python で解く: Chapter 2