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

【LeetCode数据结构】单链表的应用——反转链表问题、链表的中间节点问题详解

ds 2025/7/14 8:34:03

🔥个人主页：艾莉丝努力练剑

❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题

🍉学习方向：C/C++方向

⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平

前言：牛客网和LeetCode的刷题都不可或缺，我们都要做一做，无论是参加竞赛还是笔试面试，至少能提升你的代码能力！洛谷的题目也可以去做一做。力扣的题目对提升代码能力很有帮助，需要有一点基础，几乎都是接口型的题目，关于接口型和IO型的区别我们在本专栏的第一篇【LeetCode】力扣题——轮转数组、消失的数字、数组串联中就介绍过了，这里不再赘述。

正文

一、反转链表问题

206.反转链表

博主题解链接：三指针解决反转链表问题

大家可以直接去看博主在力扣上面写的题解，还是比较详细的。

题目描述：

像这种题目拿到手我们首先就是想到要画图，一定要有这个意识，数据结构的算法题一定要画图。

比如我们这里直接把题目中示例1的示例图截图扣下来，粘贴到画图板上——

接下来才能有思路——

1、思路

我们选用的方法：创建三个指针，改变指针的指向。

2、解题过程

如下图所示——

代码演示：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) 
{if(head == NULL){return head;}//创建三个指针ListNode* n1,*n2,*n3;if(n2)n1 = NULL,n2 = head,n3 = n2->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3)n3 = n3->next;}return n1;
}

复杂度：时间复杂度: O(N) ，空间复杂度: O(1) 。

3、另外的思路

有思路2就肯定有思路1，只不过思路1大家都想得到，不太有讲解的必要。

思路1：创建新链表，遍历原链表，将头节点插到新链表中——

时间复杂度：O(N)。

二、链表的中间节点问题

876.链表的中间节点

博主题解链接：快慢指针求解单链表中间节点问题

大家直接去看博主在力扣上面写的题解也是可以的。

题目描述：

再强调一遍，一定要有这个画图的意识，数据结构的算法题真的一定要画图。

1、思路

我们选用的方法：快慢指针

快慢指针是一个非常重要的方法，我们一定要重视。后面还会有几道题要用到快慢指针。

2、解题过程

这几次单链表相关的力扣题目，博主都用画图软件画了图，就不多赘述了，大家看图。

解题过程：创建快慢指针slow、fast，慢指针每次走一步，快指针每次走两步，我们分为奇数和偶数两种情况讨论，看两者是否满足条件——

（1）奇数

条件：fast->next != NULL;

（2）偶数

条件：fast != NULL;

非常值得注意的一点

这里表达式不能像下面图中这样写，顺序不能倒，fast != NULL一定是在前面，因为如果fast->next != NULL在前面，如果这时候偶数fast为空，&&表达式就短路了，短路了就走不到&&后面的表达式里面了，空指针不能解引用——

代码演示：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) 
{//创建快慢指针ListNode* slow = head;ListNode* fast = head;while(fast != NULL && fast->next != NULL){slow = slow->next;fast = fast->next->next;}return slow;
}

复杂度：时间复杂度: O(n)，空间复杂度: O(1) 。