面试算法题(1)--链表反转

分享一道面试碰到的算法题。
链表反转，不借助任何掐数据结构或容器。

意思就是把链表尾当成链表头，并且每个节点的指针反向。先看下图：

黑色部分是原来链表；
红色部分是翻转后的链表。




思路分析：
1、拿到head链表头，然后递归处理。
2、当处理到head节点是，需要把head的next指针置空。
3、如果是最后一个节点，需要把节点引用赋给head。
4、如果是中间的某节点，需要把其引用赋给他下一个节点的next指针。


思路理清楚了，感觉好像不难。我们开始撸代码。

public void reserve(Node node){
	//1
	if(node == null){
		//当前节点为null
		return;
	}
	//2
	if(node == head){
		//如果是head节点
		head.next = null;
	}
	//3
	if(node.next == null){
		//末尾节点
		head = node;
		return;
	}
	//4
	//获取下一个节点
	Node nextNode = node.next;
	//翻转，下一个节点的next指针指向当前node节点
	nextNode.next = node;
	reserve(nextNode);
}

分析上面2和3处的代码，
第一次调用时，传入head节点，然后就立即执行了head.next = null;
接着就会进入3处的判断。然后程序结束了？
这儿肯定有问题,head.next不应该先处理，可以放到判断3处。修改代码如下

public void reserve(Node node){
	//1
	if(node == null){
		//当前节点为null
		return;
	}
	//2.表示是末尾节点
	if(node.next == null){
		//先置空旧的head的next指针
		head.next = null;
		//把末尾节点赋给head
		head = node;
		return;
	}
	//4
	//获取下一个节点
	Node nextNode = node.next;
	//翻转，下一个节点的next指针指向当前node节点
	nextNode.next = node;
	reserve(nextNode);
}

代码撸完了，是不是上面这样的？
哈哈，有问题。为啥？你代入head节点看看。
会不会出现下面这张图的效果？

已经是死循环了，第三个节点后面的数据都弄丢了。
我们总的思路没错，但是每次都需要保存好下一个和下下一个节点。
于是修改代码：

public void preReserve(Node node){
	if(node == null || node.next == null){
		//如果当前链表头为null，或者无下一个节点。则不需要翻转
		return;
	}
	reserve(node, node.next);
}

private void reserve(Node curNode, Node nextNode){
	//1
	if(curNode == null){
		//当前节点为null
		return;
	}
	//2.表示是末尾节点
	if(nextNode == null){
		//先置空旧的head的next指针
		head.next = null;
		//把末尾节点赋给head
		head = curNode;
		return;
	}
	//4
	//获取下下一个节点
	Node nextNextNode = nextNode.next;
	//翻转，下一个节点的next指针指向当前node节点
	nextNode.next = curNode;
	reserve(nextNode, nextNextNode);
}

这回是真的撸完了，
Node nextNextNode = nextNode.next;
上面这行代码很重要。
你可以运行看看效果。


以上是我个人的思路，若你有更好的算法，欢迎留言