Pythonでリンクリストの先頭からk番目と末尾からk番目のノードを交換する方法

問題の概要

リンクリスト L と整数 k が与えられたとします。ここで求められているのは、先頭から k 番目のノードと末尾から k 番目のノードを入れ替え、その結果のリンクリストを返すことです。

たとえば、入力が L = [1,5,6,7,1,6,3,9,12]、k = 3 の場合を考えてみましょう。先頭から3番目のノードは「6」、末尾から3番目のノードは「3」です。この2つのノードの値を入れ替えると、出力は [1,5,3,7,1,6,6,9,12] となります。

解き方のアルゴリズム

この問題は、いわゆる「2つのポインタ（two-pointer）」テクニックを使うことで、リストを一度走査するだけで効率的に解けます。手順は以下の通りです。

1. temp を先頭ノード L に設定する
2. i が 0 から k-2 までの範囲で、temp を次のノードへ進める（これにより temp は先頭から k 番目のノードを指すようになる）
3. firstNode := temp とする
4. secondNode := L とする
5. temp の次のノードが null でない限り、secondNode と temp をそれぞれ次のノードへ進める
6. firstNode の値と secondNode の値を交換する
7. L を返す

なぜこれで動くのか？

まず1つ目のポインタ（temp）を先頭から k-1 ステップだけ進めます。その後、2つ目のポインタ（secondNode）を先頭に置き、1つ目のポインタが末尾に到達するまで両方を同時に進めていきます。2つのポインタの間隔は常に k-1 に保たれているため、1つ目のポインタが末尾に来た時点で、2つ目のポインタはちょうど末尾から k 番目のノードに到達しています。

なお、ここではノード自体をつなぎ替えるのではなく、ノードが持つ値（val）だけを交換している点にも注目してください。これにより、ポインタ操作によるバグを避け、シンプルに実装できます。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

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

def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head

def print_list(head):
    ptr = head
    print('[', end="")
    while ptr:
        print(ptr.val, end=", ")
        ptr = ptr.next
    print(']')

def solve(L, k):
    temp = L
    for i in range(k - 1):
        temp = temp.next
    firstNode = temp
    secondNode = L
    while temp.next:
        secondNode = secondNode.next
        temp = temp.next
    firstNode.val, secondNode.val = secondNode.val, firstNode.val
    return L

L = [1,5,6,7,1,6,3,9,12]
k = 3
print_list(solve(make_list(L), k))

入力

[1,5,6,7,1,6,3,9,12], 3

出力

[1, 5, 3, 7, 1, 6, 6, 9, 12]

計算量について

このアルゴリズムでは、リンクリストを最大2回走査しますが、いずれも線形時間で済むため、時間計算量は O(n) です。また、追加のデータ構造を使用しないため、空間計算量は O(1) となり、非常に効率的な解法といえます。