【C++】链表反转_链表反转c++代码

链表反转是C++面试经常会考的一道题目，下面介绍2种解法，分别是非递归法和递归法。

理论

1.非递归法（迭代反转）
创建3个指针pre cur nex，每个循环指针各向后移动一个节点。

2.递归法
通过不断压栈，然后退栈，先进后出。

代码实现

//test 反转链表

#include <iostream>
using namespace std;

struct ListNode
{
	int val;
	ListNode *next;
};

//打印链表
void printList(ListNode* head)
{
	while (head)
	{
		cout << head->val;
		head = head->next;
		if (head)
			cout << "->";
	}
	cout << "\n";
}

//反转链表
//1.非递归法
ListNode* reverseList1(ListNode* head)
{
	//初始化ListNode
	ListNode *pre = NULL;
	ListNode *cur = head;
	ListNode *nex = NULL;

	while (cur)
	{
		//当前链表非空，进行以下处理
		nex = cur->next;	//当前值的下一位
		cur->next = pre;
		pre = cur;	//当前值赋给pre
		cur = nex;	//下一位赋给当前值
	}
	return pre;
}

//2.递归法
ListNode* reverseList2(ListNode* head)
{
	if ( !head || !head->next)
		return head;
	ListNode *pNode = reverseList2(head->next);
	head->next->next = head;
	head->next = NULL;
	return pNode;
}

//main
int main()
{
	//创建链表
	ListNode* head = NULL;
	ListNode* cur = NULL;	//current
	for (int i = 1; i <= 6; ++i)
	{
		ListNode* node = new ListNode;
		node->val = i;
		node->next = NULL;
		if (head == NULL)
		{
			head = node;
			cur = node;
		}
		else
		{
			cur->next = node;
			cur = node;
		}
	}
	printList(head);	//打印当前链表
	printList(reverseList1(head));	//第一种方法
	//printList(reverseList2(head));	//第二种方法
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

运行结果如下：

以上。