链表反转的五种实现方法：头插法、尾插法、递归等

链表反转的五种实现方法：头插法、尾插法、递归等

引用

CSDN

1.

https://blog.csdn.net/2301_76686024/article/details/140565032

一、链表简介

链表是一种数据结构，它包括物理结构和逻辑结构；在物理结构上它表现为非连续、非顺序的性质，然而在逻辑上链表是一种顺序结构。它解决顺序表（简单理解为C语言数组）调整大小带来的数据复制问题，可以实现在O(1)的时间范围内实现插入和删除，但也失去了顺序表的随机访问特性。

其结构包括一个数据域和指针域，数据区域用于保存数据，指针域用于保存下一个元素的地址，C语言定义如下：

typedef struct Node
{
 int data;//数据域
 struct Node* next;//指针域
}*linklist,Node;

用图示表现链表为：

这里对链表不做过多介绍，需要对链表详细了解，请参考相关资料。

二、反转链表

2.1 问题引入

给定单链表的头节点 head，请反转链表，并返回反转后的链表的头节点。

示例如下：

题目来源力扣：LCR 024. 反转链表 - 力扣（LeetCode）

其节点的定义如下：

/*Definition for singly-linked list.*/
 struct ListNode {
 int val;
 ListNode *next;
 ListNode() : val(0), next(nullptr) {}
 ListNode(int x) : val(x), next(nullptr) {}
 ListNode(int x, ListNode *next) : val(x), next(next) {}
 };

2.2 简单分析——利用数组/顺序表

首先我们遍历一遍链表，并将每个节点放入到已经定义好的数组 Nodes 中，可以得到数组 Nodes 如下所示：

然后我们可以将数组 Nodes 从第 n 个元素开始，依次使其 next 区域指向前一个元素，数组第一个元素的 next 指向 NULL（如下图所示，蓝色箭头），返回数组最后一个元素，即完成链表反转。

代码实现（C++）：

ListNode* reverseList(ListNode* head) 
{
 if(head == nullptr) return head;
 vector<ListNode*>Nodes;
 ListNode* p = head;
 while(p)
 {
 Nodes.push_back(p);
 p = p->next;
 }
 int n = Nodes.size();
 for(int i = n-1;i > 0;i --)
 Nodes[i]->next = Nodes[i-1];
 Nodes[0]->next = nullptr;//修改第一元素的next为NULL
 return Nodes[n-1];
}

复杂度分析（假设链表大小为 n）：

• 时间复杂度：O(n)，遍历两遍
• 空间复杂度：O(n)，数组大小

2.3 利用栈和尾插法

创建栈 stk，利用栈存储先进后出的特性，将节点全部存入后，依次取出进行尾插法，完成链表反转。

其过程如下图所示：

直至栈为空，此时原来的链表已经反转，且头节点为 L

代码实现：

ListNode* reverseList(ListNode* head) 
{
 if(head == nullptr) return head;
 stack<ListNode*>stk;
 ListNode* p = head;
 while(p)
 {
 stk.push(p);
 p = p->next;
 }
 ListNode* L = new ListNode(-1);//新建头节点
 p = L;//尾指针
 while(!stk.empty())
 {
 ListNode* curr = stk.top();
 stk.pop();
 curr->next = nullptr;
 p->next = curr;
 p = curr;
 }
 p = L->next; 
 delete L;
 return p;
}

复杂度分析（假设链表大小为 n）：

• 时间复杂度：O(n)，遍历两遍
• 空间复杂度：O(n)，栈空间大小

2.4 “优雅”遍历——递归

有了2.3的思路，自然可以想到递归的压栈操作，可以先利用递归遍历，直到发现其 next 为空，即最后一个节点 n，那么则开始将该节点使用尾插法插入到准好的新建链表之中，之后递归返回到第 n-1 个节点，重复上述操作，其过程与栈类似。

如下图所示：

代码实现：

ListNode* l;
ListNode* p;
void func(ListNode* head)
{
 if(head == NULL) return ;
 func(head->next);
 //返回后开始尾插
 head->next = nullptr;
 p->next = head;
 p =head;
}
ListNode* reverseList(ListNode* head) 
{
 l = new ListNode(-1);
 p = l;
 func(head);
 p = l->next;
 delete l;
 return p;
}

复杂度分析（假设链表大小为 n）：

• 时间复杂度：O(n)，遍历一遍
• 空间复杂度：O(n)，递归的深度

2.5 快速反转/头插法(原地反转)

在此方法中，我们事先建立一个新的链表 L，然后遍历原来的链表的每一个节点，用 curr 指针来指向当前节点，然后将 curr 节点从原来的链表中摘下来，并且插入到 L 的 next（利用头插法逆序，可参考前面博客看头插详细）

具体代码如下：

ListNode* reverseList(ListNode* head) 
{
 if(head == NULL) return head;
 ListNode* L = new ListNode(-1);//事先建立的链表
 ListNode* curr = head;
 while(curr)
 {
 ListNode* Temp = L->next;
 L->next = curr;
 curr = curr->next;
 L->next->next = Temp;
 }
 curr = L->next;
 delete L;
 return curr;
}

复杂度分析（假设链表大小为 n）：

• 时间复杂度：O(n)，遍历一遍
• 空间复杂度：O(1)，没有使用额外的空间