链表的两种反转

首先创建一个链表：

1
2
3
4
5
6
struct Node {
	int data;
	Node* next = NULL;
};

Node* head = NULL;//指向头部的指针

1.递归法反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
void reserve(Node *p)
{
	if (p->next == NULL)
	{
		head = p;
		return;
	}
	reserve(p->next);
	p->next->next = p;
	p->next = NULL;
	return;
}
//链表的递归反转，开始时传入头指针head

2.迭代法反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void reserveBydiedai()
{
	Node* prev = NULL;
	Node* now = head;
	Node* nex;
	while (now != NULL)
	{
		nex = now->next;
		now->next = prev;
		prev = now;
		now = nex;
	}
    
	head = prev;//最后记得更新头指针
}
//链表的迭代反转