`
java-mans
  • 浏览: 11340694 次
文章分类
社区版块
存档分类
最新评论

反转单向链表(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;	
}



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics