[Python] 連結リストを逆順にする

Python で連結リストを逆順にします。

連結リストは以下の実装を使います。

単純に考えれば、空の連結リストを用意して値を先頭から挿入していくことで、逆順の連結リストを取得できます。

def reverse_linked_list(self):
    reversed_linked_list = LinkedList()

    current_node = self.head
    while current_node:
        reversed_linked_list.insert_first(current_node.data)
        current_node = current_node.next_node

    return reversed_linked_list

連結リストの先頭への挿入は\( O (1) \) なので時間計算量は\( O(N)\)ですが、コピー先の分で空間計算量も\( O(N) \) になります。

現在のノード、前のノード、次のノードの3つを把握し、現在のノードから前のノードへポインタを付け替える操作を繰り返し行うことで、この操作の空間計算量を\(O(1)\)にすることができます。

def reverse_linked_list_inplace(self):
    current_node = self.head
    previous_node = None

    while current_node:
        # ポインタを逆にする前に次のノードを保持
        next_node = current_node.next_node
        # 現在のノードの次のノードを前のノードに変更
        current_node.next_node = previous_node
        # ノードを一つ進める
        previous_node = current_node
        current_node = next_node

    # 一番最後に head を変更
    self.head = previous_node

まとめます。

class Node(object):

    def __init__(self, data):
        self.data = data
        self.next_node = None


class LinkedList(object):
    
    def __init__(self):
        self.head = None
        self.length = 0
    
    # O(1)
    def insert_first(self, data):

        new_node = Node(data)
        self.length += 1

        if not self.head:
            self.head = new_node
        else:
            new_node.next_node = self.head
            self.head = new_node

    # O(N)
    def __str__(self):
        elems = ''
        current_node = self.head
        while current_node:
            if current_node.next_node is None:
                elems += str(current_node.data)
            else:
                elems += str(current_node.data) + ', '
            current_node = current_node.next_node
        return '[' + elems +']'

    # O(1)
    def __len__(self):
        return self.length
    
    # O(N)
    def insert_last(self, data):

        if self.head is None:
            self.insert_first(data)
        else:
            new_node = Node(data)
            self.length += 1
            current_node = self.head

            while current_node.next_node is not None:
                current_node = current_node.next_node
            
            current_node.next_node = new_node

    # 追加
    # O(N)
    def remove(self, data):

        if self.head is None:
            print('リストは空です。')
            return

        current_node = self.head
        previous_node = None

        while current_node.data != data:
            if current_node.next_node is None:
                print('削除に該当するデータがありません。')
                return 
            previous_node = current_node
            current_node = current_node.next_node
        
        # 削除ノードが先頭
        if previous_node is None:
            self.head = current_node.next_node
            self.length -= 1
        else:
            previous_node.next_node = current_node.next_node
            self.length -= 1


    def reverse_linked_list(self):
        reversed_linked_list = LinkedList()

        current_node = self.head
        while current_node:
            reversed_linked_list.insert_first(current_node.data)
            current_node = current_node.next_node

        return reversed_linked_list

    def reverse_linked_list_inplace(self):
        current_node = self.head
        previous_node = None

        while current_node:
            # ポインタを逆にする前に次のノードを保持
            next_node = current_node.next_node
            # 現在のノードの次のノードを前のノードに変更
            current_node.next_node = previous_node
            # ノードを一つ進める
            previous_node = current_node
            current_node = next_node

        # 一番最後に head を変更
        self.head = previous_node


if __name__ == '__main__':
    linked_list = LinkedList()
    
    linked_list.insert_last(1)
    linked_list.insert_last(2)
    linked_list.insert_last(3)
    linked_list.insert_last(4)
    # [1, 2, 3, 4]
    print(linked_list)

    reversed_ll = linked_list.reverse_linked_list()
    # [4, 3, 2, 1]
    print(reversed_ll)

    linked_list.reverse_linked_list_inplace()
    # [4, 3, 2, 1]
    print(linked_list)