链表反转是C 面试经常会考的一道题目，下面介绍2种解法，分别是非递归法和递归法。
理论
1.非递归法（迭代反转） 创建3个指针pre cur nex，每个循环指针各向后移动一个节点。
2.递归法 通过不断压栈，然后退栈，先进后出。
代码实现
代码语言：javascript复制//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;
}运行结果如下：
在这里插入图片描述以上。
