C语言：反转链表_反转链表c语言

思路：
1.迭代：
迭代法反转链表需要3个指针，一个是当前指针head，一个是它的前节点newhead，一个是它的后节点next。

前节点是为了构造新的链，而后节点是为了与原来的链保持联系。newhead初始化为空，next初始化为头节点的next。

令head指向newhead，然后使newhead指向这个新链。这时head与原来的链断开，next就发挥了作用，令head指向next，然后next右移。重复此操作直至next为空。

此时head指向原链中的最后一个节点，将它指向新链，至此反转链表构造完成。
2. 递归：
总的思路时创建一个pre节点，令当前节点指向pre。

当head为头节点，我们希望它的next为NULL，所以pre的初始化为空。

但如果直接使头节点的next为空，这条链就断了。所以我们希望在执行1->NULL(表示1的next为NULL)之前，节点2的next已经指向了1。

假设该单链表的结构为：

1->2->3->4->5->6->NULL

我们希望的结构可以表示为以下表格(head->pre)：

从上往下分析问题：
为使1指向NULL，需使2指向1；
为使2指向1，需使3指向2；
为使3指向2，需使4指向3；
为使4指向3，需使5指向4；
为使5指向4，需使6指向5；
为使6指向5，需初始化节点6；

从下往上解决问题：

初始化节点6： 此时链中只有一个节点，只需返回它即可。

//`ReverseList_Recursion(节点6)`的结构
if(head->next == NULL)    //此时head->val为6，heead->next为NULL
    return head;
1
2
3

使6指向5：（可看作要将链表5->6反转）
即函数ReverseList_Recursion(节点5)的返回值应是链表6->5
已知ReverseList_Recursion(节点6)返回一个单节点的链表，我们只需在它后面连接节点5即可。
具体做法为：

1. 创建一个节点记录ReverseList_Recursion(节点6)的返回值；

2. 创建一个节点记录当前head值；

3. 令ReverseList_Recursion(节点6)返回值的next指向当前head即可。

   由此便得到了递归的结构。

迭代法反转链表

void ReverseList_Iteration(Linknode* head)
{
	if ((head == NULL) || (head->next == NULL))
		return;
	Linknode* newhead = NULL;
	Linknode* next = head->next;

	while (next != NULL) 
	{
		head->next = newhead;
		newhead = head;
		head = next;
		next = next->next;
	}
	head->next = newhead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

无报错，但运行不正确。调试观察ReverseList_Iteration函数结束后链表的情况：

可以看到ReverseList_Iteration函数结束时链表已正确反转。

继续执行：

可以看到执行完反转函数后，链表中仅剩余一个值，变成了单节点。

错误原因未知
看着像是传值和传址的区别，但是形参为指针传递的不是地址吗？改变也是对原来地址上的变量进行改变，为什么对形参做的改变返回后会无效呢？

修改1：将反转函数总的形参变为指向 指向链表的指针 的指针（二级指针）。

void ReverseList_Iteration(Linknode** head)
{
	if ((head == NULL) ||  (*head == NULL) || ((*head)->next == NULL))
		return;
	Linknode* newhead = NULL;
	Linknode* next = (*head)->next;

	while (next != NULL)
	{
		(*head)->next = newhead;
		newhead = *head;
		*head = next;
		next = next->next;
	}
	(*head)->next = newhead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

注意：->的优先级比*高，因此要表示head链表的next值时，应使用：

(*head)->next = 具体值;

修改2：令反转函数返回修改后的链表。

Linknode* ReverseList_Iteration(Linknode* head)
{
	if ((head == NULL) || (head->next == NULL))
		return head;
	Linknode* newhead = NULL;
	Linknode* next = head->next;

	while (next != NULL) 
	{
		head->next = newhead;
		newhead = head;
		head = next;
		next = next->next;
	}
	head->next = newhead;
	return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

运行结果：

两种改法均可以成功反转链表。

递归反转链表

Linknode* ReverseList_Recursion(Linknode* head)
{
	Linknode* pre = NULL;

	if (head == NULL)
		return NULL;
	if (head->next == NULL)
		head->next = pre;
		return head;

	pre = head;
	head = ReverseList_Recursion(head->next);
	head->next = pre;

	return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

运行结果：

主函数与头文件与前几个题目类似，就不再写了。