您现在的位置是：首页 >技术交流 >【数据结构】--单链表力扣面试题②反转链表网站首页技术交流

目录

 法一：直接反转法

法二：头插法

题述：给你单链表的头结点head，请你反转链表，并返回反转后的链表。

题目已知链表创建，并给了reverseList的函数头。

struct ListNode* reverseList(struct ListNode* head)

 

示例3：

输入：head = [ ]

输出：[ ]

思考：创建一个新链表，然后值是逆置的行吗？不行！因为题目要求的是在原链表上逆置，改变原链表的指向，并不是值的拷贝后的逆转。那其实总共有三种方法。法一，直接原地翻转。法二，头插法。法三，递归法。这里讲解法一法二。因为能用循环就用循环，没必要用递归，因为递归有缺陷，如果链表够长的话，肯呢个会造成栈溢出，栈的空间本来就不大。

 法一：直接反转法

思路：数据结构解题关键步骤：画图+写代码/调试（解题关键）

那么我们的思路可以是定义两个变量指针指向节点

 如图，我们可以让n2的next指针域指向n1,然后让n2指向现节点的下一节点，但是怎么找下一节点？遇到这种情况我们就可以再创建一个变量指针n3，这样就能找到下一节点了，因为这个过程需要遍历链表，所以需要n3

n1和n2是用来翻转链表的，n3是用来迭代的。

 一直迭代下去，终止条件：

终止条件应该就是n2==NULL,而不是第一次n3==NULL，因为此时若终止，n2的节点的指针域还未指向n1,最终可知新头结点是n1。

#include<stdio.h>
#include<stdlib.h>

struct ListNode
{
	int val;
	struct ListNode* next;
};
struct ListNode* reverseList(struct ListNode* head)
{
	if (!head)//如果为空 !NULL为真，则返回NULL
	{
		return NULL;
		//如果为空链表，则无需翻转，直接返回NULL，
		//如果此刻你不返回，那么会对NULL指针解引用，会非法访问内存
	}

	struct ListNode* n1, * n2, * n3;
	n1 = NULL;
	n2 = head;
	n3 = head->next;

	while (n2)//通过画图可知，n2为空时就是翻转完毕的时候
	{
		n2->next = n1;//翻转链表

		n1 = n2;//迭代
		n2 = n3;//迭代
		if (n3)//如果n3已经为NULL了，就没有必要走这个循环了
			n3 = n3->next;
	}

	return n1;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;

	struct ListNode* head = reverseList(n1);
	struct ListNode* cur;
	for (cur = head; cur != NULL; cur = cur->next)
		printf("%d ", cur->val);

	return 0;
}

法二：头插法

思路：取原链表中的节点，头插到新链表newhead中。

 但是这里有一个疑问，怎么找到此节点的下一节点，他的指针域已经指向了新的头，所以同理，我们还是再创建一个变量next保存下一节点。

#include<stdio.h>
#include<stdlib.h>

struct ListNode
{
	int val;
	struct ListNode* next;
};
struct ListNode* reverseList(struct ListNode* head)
{//这种情况不用格外考虑是不是空链表的问题，因为如果是，循环都进不去，直接返回NULL
	struct ListNode* cur = head;
	struct ListNode* next = NULL;
	struct ListNode* newhead = NULL;
	while (cur)
	{
		next = cur->next;
		//头插
		cur->next = newhead;
		newhead = cur;
		//迭代往后走
		cur = next;
	}
	return newhead;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;

	struct ListNode* head = reverseList(n1);
	struct ListNode* cur;
	for (cur = head; cur != NULL; cur = cur->next)
		printf("%d ", cur->val);

	return 0;
}