经典算法——单向链表反转

恋喵大鲤鱼

发布于 2019-06-24 10:04:07

7.9K0

发布于 2019-06-24 10:04:07

1. 题目

单向链表反转是一道经典的求职面试笔试或机试题。给定如下如下链表的节点定义：

struct LinkNode
{
	int value;
	LinkNode* next;
};

比如有一个链表是这样的，1->2->3->4->5，反转后成为 5->4->3->2->1。请实现函数

LinkNode* Reverse(LinkNode* header);

2. 迭代实现

2.1 分析

实现链表反转，我们需要从第二个节点开始遍历，将当前节点的 next 指向前一个节点。这里需要注意的是，该变当前节点的 next 时，需要提前保存 next，不然遍历就会中断。

时间复杂度 O(n)；空间复杂度 O(1)。

2.2 实现

//@brief: 迭代方式，实现单向链表反转
LinkNode* Reverse(LinkNode* header)
{
	if (header == NULL || header->next == NULL)
	{
		return header;
	}
	
	LinkNode* pre = header, *cur = header->next;
	pre->next = NULL;
	while(cur != NULL)
	{
		auto next = cur-> next;
		cur->next = pre;
		pre = cur;
		cur = next;
	}
	return pre;
}

2.3 验证

//
//@brief: main.cpp
//

#include <iostream>
using namespace std;

//@brief: 打印单向链表
void printLink(LinkNode* header)
{
	while(header != NULL)
	{
		cout<< header->value;
		header = header->next;
		if (header != NULL)
		{
			cout<< "->";
		}
	}
	cout<<endl;
}

int main(int argc, char* argv[])
{
	//创建单向链接
	LinkNode* header = NULL, *cur = NULL;
	for(int i = 1; i <= 5; ++i) 
	{
		LinkNode* node = new LinkNode;
		node->value = i;
		node->next = NULL;
		
		if (header == NULL)
		{
			header = node;
			cur = header;
		}
		else
		{
			cur->next = node;
			cur = node;
		}
	}
	
	printLink(header);
	
	//反转单向链表
	auto newHeader = Reverse(header);
	
	printLink(newHeader);
}

编译执行输出：

g++ -std=c++11 main.cpp
./a.out
1->2->3->4->5
5->4->3->2->1

3. 递归实现

3.1 分析

从倒数第二个节点开始反转，依次向前，将后一个节点的 next 指向当前节点。注意每次反转后要将当前节点的 next 置空，表示断开当前节点与后一个节点的关联。此种方法可以使用递归来实现。

时间复杂度 O(n)；空间复杂度 O(n)。

由于每次递归都需要为实参分配空间，所以相较于非递归实现，较为耗费栈空间，且不易理解。

3.2 实现

//@brief: 递归方式，实现单链表反转
LinkNode * Reverse(LinkNode * head)
{
	//递归终止条件：找到链表最后一个结点
	if (head == NULL || head->next == NULL)
	{
		return head;
	}
	
	LinkNode * newhead = ReverseList(head->next);	//先递后归，从后往前遍历每个节点进行反转
	head->next->next = head;	//将当前节点的后一个节点的  next 指向当前结点
	head->next = NULL;			//断开当前节点指向后一个节点
	return newhead;
}

参考文献

[1] 经典算法——单链表反转的递归方法和非递归方法

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019年06月22日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度