反转链表的四种方式

大家好，欢迎来到IT知识分享网。

链表反转的四种方式

一：原地反转

原地反转需要用两个指针进行移动去完成

假设原链表如图：

我们定义了两个指针：beg和end,并将他们指向L->next和L->next->next:

beg=L->next; end=L->next->next; 

下面是具体步骤：

1.连

第一步我们需要把beg的指针域移向end->next：

beg->next=end->next; 

2.掉

第二步我们需要把end指针域指向L->next:

end->next=L->next; 

3.接

第三步我们需要把头结点的指针域指向end:

L->next=end; 

4.移

第四步我们要把end，向后移动，移向end->next，方便进行下一次的操作:

end=beg->next; 

第一轮操作完成后链表变成了下图：

我们会发现链表正在慢慢地反转，我们只需要不断地重复进行（连掉接移），就可以实现链表的反转：

此时我们如果把end继续向后移动，我们就会发现end指向了NULL，所以我们也找到了循环终止的条件(end==NULL)。

总代码

下面是完整代码：

void Reserve(Linklist L) { 
    if(L==NULL||L->next==NULL) return; LNode* beg=L->next; LNode* end=L->next->next; while(end!=NULL){ 
   //终止条件 beg->next=end->next;//连 end->next=L->next;//掉 L->next=end;//接 end=beg->next;//移 } } 

二：头插法

我们只需要用头插法的方式把原链表的数据一一插入，就能达到反转的效果

我们需要创建指针进行移动指向原链表的数据

我们首先需要创建一个指针p指向L->next：

p=L->next; 

然后我们就可以断开L与第一个节点了，让L->next指向NULL:

L->next=NULL; 

这里我们就完成了准备工作。

1

我们需要创建一个指针q指向p的下一个节点：

q=p->next; 

2

然后我们需要把p->next指向L->next：

p->next=L->next; 

3

然后把L->next指向p:

L->next=p; 

4

接下来就是为下一个循环做准备

让p指向q，再把q移动向下一位：

p=q; //q=p->next 第一步 

当我们最后一次执行q=p->next(NULL)时跳出循环，反转结束。

总代码

下面是完整代码：

void Reserve(LinkList L) { 
    if(L==NULL||L->nest==NULL){ 
    return; } LNode *p,*q; p=L->next; L->next=NULL; while(p!=NULL){ 
    q=p->next; p->next=L->next; L->next=p; p=q; } } 

三：迭代法

迭代法我们需要用三个指针完成，分别是前驱节点（pre），当前节点（cur），后驱节点（next）。

1.创建节点

ListNode* pre=NULL;//前驱节点 ListNode* cur=head;//当前节点 ListNode* next=NULL;//后驱节点 

2.反转主体

while(cur!=NULL){ 
    next=cur->next;//让next指向cur的后一个节点 cur->next=pre;//让当前节点指针域指向前一个节点 pre=cur;//把前驱节点向后移动 cur=next;//把当前节点也向后移动 } 

总代码

下面是完整代码：

ListNode* Reverse(ListNode* head) { 
    ListNode* pre=NULL; ListNode* cur=head; ListNode* next=NULL; while(cur!=NULL){ 
    next=cur->next; cur->next=pre; pre=cur; cur=next; } return pre; } 

四：递归法

递归法其实理解起来还是有点难度的，主要需要我们明白递和归分别实现了什么

总代码

直接展示完整代码：

ListNode* Reverse(struct ListNode* head){ 
    struct ListNode* pre =NULL; if (head == NULL || head->next == NULL) { 
    return head; } struct ListNode *newHead = Reverse(head->next); //进行递归，找到最后一个节点后返回 head->next->next = head; //把当前节点的下一个节点指针指向这个节点，不断归，实现链表的反转 head->next = NULL; return newHead;//最后返回新的头结点 } 

参考视频：终于把单链表反转搞明白了(一)_带头节点的单链表原地反转

终于把单链表反转搞明白了(二)_带头节点的单链表反转_头插法

【LeetCode75】第三十一题 反转链表

参考文献：单链表的相关操作

已经到底啦！！