反転一方向チェーンテーブル(reverse a singly linked list)(単一反転)[#7]


質問:
一方向チェーンテーブルをあげて、最初から最後まで反転します.例えば,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;	
}