反転一方向チェーンテーブル(reverse a singly linked list)(単一反転)[#7]
質問:
一方向チェーンテーブルをあげて、最初から最後まで反転します.例えば,a->b->c->dは逆にd->c->b->aである.
ここでは2つの方法を説明します.
1つ目の方法は、ノードごとに1つのstackに順番に格納することです.そうすると、一番後ろの1つが一番上になります.そして、一つ一つ取り出して順番を変えていきます.
2つ目の方法は、2つのポインタを使用して、前のノードと現在のノードをそれぞれ指し、現在のノードと次のノードの反転が完了するたびに、最後のノードに達するまで2つのノードを下に移動することです.
一方向チェーンテーブルをあげて、最初から最後まで反転します.例えば,a->b->c->dは逆にd->c->b->aである.
ここでは2つの方法を説明します.
1つ目の方法は、ノードごとに1つのstackに順番に格納することです.そうすると、一番後ろの1つが一番上になります.そして、一つ一つ取り出して順番を変えていきます.
public static Node reverse(Node head) {
Stack<Node> stack = new Stack<Node>();
// put all the nodes into the stack
while (head != null) {
stack.add(head);
head = head.next();
}
//reverse the linked list
Node current = stack.pop();
head = current;
while (stack.empty() != true) {
Node next = stack.pop();
//set the pointer to null, so the last node will not point to the first node.
next.setNext(null);
current.setNext(next);
current = next;
}
return head;
}
2つ目の方法は、2つのポインタを使用して、前のノードと現在のノードをそれぞれ指し、現在のノードと次のノードの反転が完了するたびに、最後のノードに達するまで2つのノードを下に移動することです.
public static Node reverse(Node head) {
Node previous = null;
while (head != null) {
Node nextNode = head.next();
head.setNext(previous);
previous = head;
head = nextNode;
}
return previous;
}