リンクリストを逆さにする。

1年 ago

2 minutes

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

リンクリストを逆にする

LinkedListは、データを連続的ではない方法で保存するデータ構造です。LinkedListの各要素は、データ部と次の要素へのアドレスを含んでいます。LinkedListの要素は一般的にノードと呼ばれています。

ダブルリンクドリストは、2つのアドレスを格納します。一つは前の要素のアドレスで、もう一つは次の要素のアドレスです。

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

Iterative Approach
Recursive Approach

連結リストを逆にするための反復的な方法

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

次に、LinkedListを逆にするためになるべく以下のステップを実行してください。current、next、previousの3つのインスタンスを作成してください。currentがnullでない限り、以下の処理をループさせます。

Save the next Node of the current element in the next pointer.
Set the next of the current Node to the previous. This is the MVP line.
Shift previous to current.
Shift the current element to next.

最終的に、現在の要素は最後の要素よりも1つ先の場所に移動しているため、先に到達した最後の要素をheadに設定する必要があります。これはpreviousで利用できます。headをpreviousに設定してください。そして、古いLinkedListの最後の要素が新しいLinkedListの新しいheadとなります。

ここにLinkedListの非常にシンプルな実装があります。これは、本番向けの実装ではなく、リンクリストを逆にするアルゴリズムに焦点を合わせるためにシンプルにしてあります。

package com.scdev.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プログラムです。

package com.scdev.linkedlist.reverse;

import com.scdev.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つの部分に分ける必要があります：ヘッドと残りの部分です。ヘッドは最初の要素を指します。残りの部分はヘッドから次の要素を指します。

最終要素に到達するまで、私たちはLinkedListを再帰的にたどります。最後の要素に到達したら、それをヘッドとして設定します。その後、LinkedListの開始地点に到達するまで以下の操作を行います。node.next.next = node; node.next = null; 元のヘッドを追跡するために、ヘッドのインスタンスのコピーを保存します。

上記の手順のイラストは以下の通りです。LinkedListを再帰的に逆順にするための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リポジトリから、完全なコードとさらに多くのDS＆アルゴリズムの例をチェックアウトできます。