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

反转链表（精美图示详解哦）

news 2025/7/29 11:57:13

全文目录

引言
反转链表
- 题目描述与思路
- 实现
总结

引言

在学习了单链表的相关知识后，尝试实现一些题目可以帮助我们更好的理解单链表的结构以及对其的使用。

从这篇文章开始，将会介绍一些编程题来帮助我们更好的掌握单链表：
分别是反转链表、链表的中间结点、链表的倒数第k个结点、合并两个有序链表。

本篇文章将介绍反转链表：

反转链表OJ链接

反转链表

题目描述与思路

在这里插入图片描述
这道题要求我们实现将一个单链表反转。即原来是结点的数据依次为1，2，3，反转后的链表为3，2，1。函数的参数为链表第一个结点的地址。结构体变量与主函数部分已经定义，我们只需要实现接口即可。

之前我们实现过将一个数组的元素反转：
left为首元素的地址；right为尾元素的地址。我们可以通过循环的方式，每次用一个临时变量来帮助我们将left指向的元素与right指向的元素互换，left++、right–，直到left与right相遇时即转换完毕。

//循环例
while (left < right)
{int temp = *right;*right = *left;*left = temp;left++;right--;
}

但是，这样的思路对于反转单链表而言，显然是不能实现的。因为对于单链表而言，想要由最后一个结点访问到倒数第二个结点是不能实现的。

我们直到，链表在存储数据时，只是逻辑上连续，物理空间上是不连续的。
所以我们可以尝试改变单链表的逻辑链接刺绣，从而实现反转链表：

我们可以使链表中，后一个结点的next成员指向前一个链表的地址。将第一个结点的next成员改为NULL，原来指向第一个结点的head指针改为最后一个结点的地址。
这样，就可以实现从head开始，倒着连接单链表。

实现

为了实现上面简述的思路，我们可能需要三个结构体指针：

struct ListNode* beforecur;
struct ListNode* cur;
struct ListNode* aftercur;

cur用于遍历整个链表，beforecur指向cur前面的一个结点。
在每次循环中，我们需要将cur的next成员改为cur前面的结点的指针，即beforecur。
在每次赋值完后，beforecur需要向后移动到下一个结点的位置，将beforecur赋值为cur即可。

但是当cur->next被改变后，cur与其下一个结点的逻辑连接就会断掉，我们就不能访问到cur的下一个结点了。所以，我们需要在cur->next的值改变之前，将其赋给aftercur。这样我们就可以在下一次循环时，将cur赋值为aftercur从而实现cur移动到下一个结点的位置。

同样的，将beforecur赋值为cur需要在cur被改变前：
在这里插入图片描述

循环结束后，我们还需要将head的值改为beforecur，即让head指向单链表的最后一个结点（由于在最后一次循环后，beforecur与cur都已经向后移动过了，beforecur指向的是最后一个结点）：
在这里插入图片描述

struct ListNode* reverseList(struct ListNode* head) 
{typedef struct ListNode ListNode;ListNode* beforecur = NULL;ListNode* cur = head;ListNode* aftercur = head;while (aftercur){aftercur = cur->next;cur->next = beforecur;beforecur = cur;cur = aftercur;}head = beforecur;return head;
}