LinkedListのノードの接続を逐一逆にしていくことで、線形時間による配列のリバースを実現してみます。
目次
Node<T>
一番シンプルなノードにします。
public class Node<T extends Comparable<T>> {
private T data;
private Node<T> next;
public Node(T data) {
this.data = data;
this.next = null;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
}LinkedListクラス
public class LinkedList<T extends Comparable<T>> {
private Node<T> head;
public LinkedList(){
this.head = null;
}
public LinkedList(Node<T> head){
this.head = head;
}
public void add(T data){
Node<T> currNode = head;
if (currNode == null){
head = new Node<T>(data);
}else{
while(currNode.getNext() != null){
currNode = currNode.getNext();
}
currNode.setNext(new Node<T>(data));
}
}
public String toString(){
String result = "";
Node<T> currNode = head;
if (currNode == null){
return "Null";
}
while(currNode.getNext() != null){
result += currNode.getData()+"->";
currNode = currNode.getNext();
}
return result +currNode.getData() + "->Null";
}
public static void main(String[] args) {
LinkedList l = new LinkedList(new Node(0));
for (int i = 1;i<10;i++){
l.add(i);
}
System.out.println(l);
}
}
>>>
0->1->2->3->4->5->6->7->8->9->Nullリバースメソッド
ポインタをprev,curr,nextの３種類用意して、nextを主導としてheadから全域を巡回しながらノードの接続を繋ぎ変えていきます。
public void reverse(){
Node<T> prevNode = null;
Node<T> currNode = head;
Node<T> nextNode = null;
while(currNode != null){
nextNode = currNode.getNext();
currNode.setNext(prevNode);
prevNode = currNode;
currNode = nextNode;
}
head = prevNode;
}実行結果
public static void main(String[] args) {
LinkedList l = new LinkedList(new Node(0));
for (int i = 1;i<10;i++){
l.add(i);
}
System.out.println(l);
l.reverse();
System.out.println(l);
}
>>>
0->1->2->3->4->5->6->7->8->9->Null
9->8->7->6->5->4->3->2->1->0->Null
