当前位置：首页 > news >正文

数据结构-单链表的反转

news 2025/5/6 18:27:16

一直在路上

前言

本篇文章介绍反转单链表的三种方法，分别为普通方法、头插法、递归法。

一、普通方法

普通方法是从第一个结点开始反转，然后反转剩余的结点。
普通方法需要保存当前结点的前驱和后继，如果当前结点为第一个结点，则前驱设置为NULL
过程如下
在这里插入图片描述

图1.1 普通方法反转过程

具体代码如下

//常规方法反转
struct ListNode* reverseList_nomal(struct ListNode* head)
{struct ListNode* cur = head;struct ListNode* pre = NULL;	//前驱struct ListNode* post = NULL;	//后继while(cur != NULL){post = cur->next;	//保存后继，保证反转后任然可以找到下一个结点cur->next = pre;	//反转pre = cur;			//将当前结点保存为下一个结点的前驱cur =post;			//将下一个结点作为待反转结点}return pre;				//将最后一个反转结点作为新的head
}

二、头插法

头插法是将第二个结点及后面的结点一直往第一个结点的前面插入
头插法一般使用一个辅助结点作为第一个结点的前驱
过程如下
在这里插入图片描述

图2.1 头插法反转过程

具体代码如下

//利用头插法反转
struct ListNode* reverseList_headInsert(struct ListNode* head)
{//创建一个辅助结点struct ListNode* dummyNode = (struct ListNode*)malloc(sizeof(struct ListNode));dummyNode->val = -1;dummyNode->next = head;struct ListNode* curr = dummyNode->next;struct ListNode* next = NULL;while(curr->next != NULL){next = curr->next;curr->next = next->next;next->next = dummyNode->next;dummyNode->next = next;}free(dummyNode);    return next;
}

三、递归法

递归方法首先明确的是，即使递归到最后一层，各个结点之间的联系还存在
理解递归的最好方法是，选择一层进行研究，当前层需要做什么，需要返回什么
过程如下
在这里插入图片描述

图3.1 递归法反转过程

具体代码如下

struct ListNode* reverseList_recursion(struct ListNode* head) {if(head == NULL || head->next == NULL){return head;}//newHead始终指向尾结点struct ListNode* newHead = reverseList_recursion(head->next);//head->next 相当于未反转前的后继//head->next 即当前结点的后继//将后继结点的指针域指向当前结点完成反转head->next->next = head;//将当前结点的指针域断开，否则出现回环//回环的意思是当前结点的指针域指向了后继结点，后继结点的指针域指向了当前结点head->next =NULL;return newHead;
}