欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-06 10:08:21
...
分享一道面试碰到的算法题。
链表反转,不借助任何掐数据结构或容器。

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

面试算法题(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节点看看。
会不会出现下面这张图的效果?

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


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

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;
上面这行代码很重要。
你可以运行看看效果。


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





相关标签: 算法