リンクリストを逆にする

連結リストを逆にすることは、データ構造とアルゴリズムの興味深い問題です。このチュートリアルでは、連結リストを逆にするためのさまざまなアルゴリズムについて説明し、それらをJavaで実装します。

連結リストを逆にする

LinkedListは、データを線形に格納するデータ構造です。ただし、連続した方法ではありません。LinkedListの各要素には、データ部とLinkedListの次の要素へのアドレスが含まれています。LinkedListの要素は一般的にノードとして知られています。

双方向LinkedListは、前の要素と次の要素の2つのアドレスを格納します。

リンクリストをインプレースで逆転させるためには、次の要素が今度は前の要素を指すようにポインタを逆転させる必要があります。以下は入力と出力です。 リンクリストのヘッドは最初のノードです。他の要素にはこのためのアドレスが保存されていません。リンクリストのテールは最後のノードです。このノードに保存されている次のアドレスはnullです。以下の方法を使用して、ヘッドとテールも変更された状態でリンクリストを逆転させることができます：

• 反復アプローチ
• 再帰的アプローチ

リンクリストを逆転させるための反復アプローチ

LinkedListを反復的に反転させるには、次の要素と前の要素の参照を保存する必要があります。これにより、LinkedList内の次の要素へのメモリアドレスポインタを交換する際に、参照が失われないようにします。次の図は、参照を変更してLinkedListを反転させる方法を示しています。以下はLinkedListを反転させるために実行する手順です。

次の条件がnullでない限り、以下を繰り返します：

• 現在の要素の次のノードをnextポインタに保存します。
• currentノードの次をpreviousに設定します。これがMVP行です。
• previousをcurrentにシフトします。
• current要素をnextにシフトします。

最後に、currentが最後の要素の一つ先に進んでしまったため、headを到達した最後の要素に設定する必要があります。これはpreviousにあります。headをpreviousに設定します。これにより、LinkedListの新しいヘッドが、古いLinkedListの最後の要素になります。

以下はLinkedListを反復的に反転させてその要素を表示するための非常にシンプルな実装です。これは本番向けの実装ではなく、LinkedListを反転させるアルゴリズムに焦点を当てるためにシンプルに保っています。

package com.journaldev.linkedlist.reverse;

public class MyLinkedList {

	public Node head;

	public static class Node {

		Node next;

		Object data;

		Node(Object data) {
			this.data = data;
			next = null;
		}
	}
}

以下のJavaプログラムは、LinkedListを反復的に反転させてその要素を表示します。

package com.journaldev.linkedlist.reverse;

import com.journaldev.linkedlist.reverse.MyLinkedList.Node;

public class ReverseLinkedList {

	public static void main(String[] args) {
		MyLinkedList myLinkedList = new MyLinkedList();
		myLinkedList.head = new Node(1);
		myLinkedList.head.next = new Node(2);
		myLinkedList.head.next.next = new Node(3);

		printLinkedList(myLinkedList);
		reverseLinkedList(myLinkedList);
		printLinkedList(myLinkedList);

	}

	public static void printLinkedList(MyLinkedList linkedList) {
		Node h = linkedList.head;
		while (linkedList.head != null) {
			System.out.print(linkedList.head.data + " ");
			linkedList.head = linkedList.head.next;
		}
		System.out.println();
		linkedList.head = h;
	}

	public static void reverseLinkedList(MyLinkedList linkedList) {
		Node previous = null;
		Node current = linkedList.head;
		Node next;
		while (current != null) {
			next = current.next;
			current.next = previous;
			previous = current;
			current = next;
		}
		linkedList.head = previous;
	}

}

出力：

1 2 3 
3 2 1 

リンクリストを再帰的に反転する

リンクリストを再帰的に反転するには、リンクリストを2つの部分に分ける必要があります：ヘッドと残りの部分です。ヘッドは最初の要素を指します。残りは、ヘッドから次の要素を指します。

リンクリストを再帰的にトラバースし、最後から2番目の要素に到達するまで続けます。最後の要素に到達したら、それをヘッドとして設定します。そこから、リンクリストの先頭に到達するまで、次のように行います。node.next.next = node; node.next = null; 元のヘッドを追跡しないようにするために、ヘッドのインスタンスのコピーを保存します。

上記手順のイラストは以下の通りです。リンクリストを再帰的に反転するJavaプログラムは次の通りです：

public static Node recursiveReverse(Node head) {
	Node first;

	if (head==null || head.next == null)
		return head;

	first = recursiveReverse(head.next);
	head.next.next = head;
	head.next = null;

	return first;
}

再帰呼び出しでhead.nextを渡すだけで、リンクリストの末尾に到達します。末尾に到達したら、最後から2番目の要素を最後の要素の次に設定し、最後から2番目の要素の次のポインタをNULLに設定します。最後の要素は新しいヘッドとしてマークされます。再帰的なアプローチを使用してリンクリストを反転するには、次のコードを使用します。

myLinkedList.head = recursiveReverse(myLinkedList.head);

出力は前の反復的なアプローチと同じになります。

リンクリストを逆にするのにかかる空間時間の複雑さ

時間の複雑さ – O(n) 空間の複雑さ – O(1)

完全なコードやその他のデータ構造とアルゴリズムの例は、GitHubリポジトリから確認できます。