算法通关村第二关——终于学会链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法通关村第二关——终于学会链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

LeetCode206 给我们单链表的头结点head，请你反转链表，并返回反转后的链表，如图所示：

算法通关村第二关——终于学会链表,算法,链表,数据结构

本题有两种方法，分别为建立虚拟头结点辅助反转以及直接操作链表实现反转，两种方法我将逐一分析讲解。

1.建立虚拟头结点辅助反转

首先从名字分析一下这种方法，虚拟头结点，顾名思义，我们可以建立一个虚拟的头结点指向反转后的链表的头结点，那么，我们每次只需要将旧链表中的一个结点“拆下来”，让它指向虚拟头结点指向的结点，而虚拟头结点则指向该结点，这就实现了一次调整，多次调整，直到旧链表为空，即链表反转成功。

算法通关村第二关——终于学会链表,算法,链表,数据结构

这个方法的最主要思想就是“拆” “拆”“拆”，从图上可以直观的看到，每一步的操作就是将待处理链表的头结点拆下来，并将该结点指向虚拟头结点所指向的结点，而虚拟头结点则指向该结点，大家认真理解这幅图，这个方法就可以完全掌握了，代码如下：

struct Listnode* reverseList(Listnode* head)
{
	Listnode* ans = (Listnode*)malloc(sizeof(Listnode));//ans为虚拟头结点
	ans->val = -1;
	ans->next = NULL;
	Listnode* cur = head;//cur指针指向链表的头结点
	while (cur != NULL)
	{
		Listnode* next = cur->next;//用next指针记录下一次要操作的结点
		cur->next = ans->next;//将当前结点的下一个结点指向虚拟结点的下一个结点
		ans->next = cur;//虚拟结点指向当前结点
		cur = next;//将当前结点指向提前记录好的即将操作的结点
	}
	return ans->next;//返回虚拟结点的下一个结点，即链表的真正头结点
}

2.直接操作链表实现反转

这种方法呢，比第一种方法难理解，但是面试中经常用到，所以大家也需要重点掌握。

算法通关村第二关——终于学会链表,算法,链表,数据结构

从图上可以看到，共使用了三个指针，cur指向旧链表的头结点，pre指向新链表的头结点，而next则指向下一步想要操作的结点，每一步操作呢，我们需要先将下一步想要操作的结点保存下来（为什么要进行保存呢？是因为后续操作会改变cur->next，所以我们需要提前记录），之后我们需要将旧链表的头结点，即当前指向的结点指向新链表的头结点，并将新链表的头结点进行更新，cur指向提前保存的下一步操作需要操作的结点，重复以上步骤，直到旧链表为空，代码如下：

//直接操作链表实现反转
struct Listnode* reverseList(Listnode* head)
{
	Listnode* cur = head; //cur指针指向当前链表的头结点
	Listnode* pre = NULL;//pre指针指向调整好的新链表的头结点
	while (cur != NULL) //如果当前指向的结点不为空
	{
		Listnode* next = cur->next;//用next指针记录下一次要操作的结点
		cur->next = pre;//将当前结点的下一个结点指向新链表的头结点
		pre = cur;//更新新链表的头结点为当前结点
		cur = next;//将当前结点指向提前记录好的即将操作的结点
	}
	return pre;//返回新链表的头结点
}

文章来源地址https://www.toymoban.com/news/detail-606009.html

到了这里，关于算法通关村第二关——终于学会链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！