Pythonで連結リストを先頭と末尾から交互に並べ替える方法

片方向連結リスト(単方向リンクリスト)が与えられたとき、ノードを「末尾のノード → 先頭のノード → 末尾から2番目のノード → 先頭から2番目のノード…」という順序で並べ替えることを考えます。

例えば、入力が [1,2,3,4,5,6,7,8,9] の場合、出力は [9, 1, 8, 2, 7, 3, 6, 4, 5] となります。

解決のための手順

この問題は、以下の手順で解くことができます。

1. 現在のノード c を先頭ノードに設定し、値を一時保存するための空のリスト l を用意します。
2. c が null でない間、c の値をリスト l の末尾に追加し、c を次のノードへ進めます。これですべてのノードの値がリストにコピーされます。
3. c を再び先頭ノードに戻します。
4. c が null でなく、かつリスト l が空でない間、以下を繰り返します。
   • リスト l の末尾の要素を取り出して c の値に代入し、c を次のノードへ進めます。
   • c が null になった場合は、そこでループを抜けます。
   • そうでなければ、リスト l の先頭の要素を取り出して c の値に代入し、c を次のノードへ進めます。
5. 最後にノードを返します。

実装例

それでは、以下の実装を見て理解を深めましょう。

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(']')

class Solution:
    def solve(self, node):
        c = node
        l = []
        while c:
            l.append(c.val)
            c = c.next

        c = node
        while c and l:
            c.val = l.pop()
            c = c.next
            if c == None:
                break
            c.val = l.pop(0)
            c = c.next
        return node

ob = Solution()
head = make_list([1,2,3,4,5,6,7,8,9])
print_list(ob.solve(head))

入力

[1,2,3,4,5,6,7,8,9]

出力

[9, 1, 8, 2, 7, 3, 6, 4, 5]

アルゴリズムのポイント

この手法では、まず連結リストのすべての値をPythonのリストにコピーします。その後、pop() でリストの末尾から、pop(0) でリストの先頭から交互に値を取り出しながら、元の連結リストの各ノードに書き戻していきます。

この方法の利点は、複雑なポインタ操作を行うことなく、ノードの値の書き換えだけで目的の順序を実現できる点です。計算量はノード数を n とすると O(n)、必要な追加メモリも O(n) となります。