Pythonで連結リストを奇数番目・偶数番目のノードに並べ替える方法

問題の概要

片方向連結リスト（単方向リンクリスト）が与えられたとき、奇数番目のノードをすべて先頭に集め、その後に偶数番目のノードを続けるように並べ替えることを考えます。ここで重要なのは、「奇数・偶数」が指すのはノードが保持する値ではなく、リスト内でのノードの位置だという点です。さらに、余分なメモリを消費しないよう、インプレース（その場）で処理することが求められます。

たとえば、ノードが [1, 22, 13, 14, 25] の場合、結果は [1, 13, 25, 22, 14] となります。1番目・3番目・5番目のノード（1, 13, 25）が前半に、2番目・4番目のノード（22, 14）が後半に移動しているのがわかります。

解決のためのアプローチ

この問題は、2つのポインタを使うことで効率的に解決できます。1つ目のポインタ（head1）は奇数位置のノード列を、2つ目のポインタ（head2）は偶数位置のノード列をそれぞれ追跡します。各ノードの next ポインタを付け替えながらリストを進め、最後に奇数列の末尾へ偶数列の先頭をつなげれば完成です。

アルゴリズムの手順

• head が NULL、または head の次のノードが NULL の場合は、ノードが1つ以下であるため、そのまま head を返します。
• head1 := head、head2 := head.next、head2_beg := head.next として初期化します（head2_beg は偶数列の先頭を記憶しておくための変数です）。
• head2.next が NULL でなく、かつ head2.next.next も NULL でない間、次の処理を繰り返します。
  • head1.next := head2.next（奇数列に次の奇数ノードを接続）
  • head2.next := head2.next.next（偶数列に次の偶数ノードを接続）
  • head1 := head1.next、head2 := head2.next として両ポインタを前進させます。
• ループ終了後、head2.next が NULL でない場合は、残りのノードを奇数列に接続します。
• head1.next := head2_beg として奇数列の末尾に偶数列の先頭をつなぎ、head2.next := NULL として偶数列の末尾を閉じます。
• head を返します。

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(']')
class Solution(object):
    def oddEvenList(self, head):
        if head == None or head.next ==None:
            return head
        head1=head
        head2,head2_beg= head.next,head.next
        while head2.next!= None and head2.next.next!= None:
            head1.next = head2.next
            head2.next = head2.next.next
            head1 = head1.next
            head2 = head2.next
        if head2.next!=None:
            head1.next = head2.next
            head1 = head1.next
        head1.next = head2_beg
        head2.next = None
        return head
ob1 = Solution()
head = make_list([1,22,13,14,25])
print_list(ob1.oddEvenList(head))

入力

[1,22,13,14,25]

出力

[1, 13, 25, 22, 14]

計算量について

このアルゴリズムはリスト全体を一度だけ走査するため、時間計算量は O(n) です。また、新しいリストや追加のデータ構造を作成せず、既存のノードのポインタを付け替えるだけなので、空間計算量は O(1) となり、メモリ効率の良いインプレース処理が実現できます。