反转单向链表（reverse a singly linked list）(单个反转) [# 7]

问题：

给一个单向链表，把它从头到尾反转过来。比如： a -> b -> c ->d 反过来就是 d -> c -> b -> a 。

这里讲解两种方法：

第一种方法就是把每个Node按照顺序存入到一个stack里面，这样，最后面一个就在最上面了。然后，把每一个再取出来，这样顺序就换过来了。

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;	
}

第二种方法就是利用两个指针，分别指向前一个节点和当前节点，每次做完当前节点和下一个节点的反转后，把两个节点往下移，直到到达最后节点。

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;	
}