目录
前言
题目
规律
思路
代码实现
前言 小伙伴们大家好,今天小编为大家带来一篇力扣上与链表有关的一个题目:反转链表。
如下图所示,我们需要将正好回文的链表的所有元素做一个反转,如下图所示:
文章图片
题目 正如上面提到的一样,题目如下所示:
文章图片
规律 规律:我们发现,其实反转也就是相当于将源链表的 “箭头” 的方向正好全部反过来。
那么既然是相当于将原链表的 “箭头” 的方向反过来,那么怎样做才能将箭头反过来呢?
这里我们提供了如下所示这样一种思路。
思路 首先,我们需要三个指针,然后第一个指针 n1 指向原链表之前的节点(第一次该节点是不存在的),第二个指针 n2 指向原链表的头节点,第三个指针 n3 指向原链表头指针的下一个节点。如下图所示:
文章图片
然后最主要的一步,我们需要将 n2 指针的 next 指向 n1,也就是反转箭头。这里我们主要的思想就是这一步骤了。如下图所示:
文章图片
之后就是三个指针同时往后移动一位,这里其实 n3 节点,就是用来记录下一个节点,然后在移动的时候就必须用到了。否则我们只用两个指针的话,下一个节点的查找就会变得很麻烦,所以这里不论从哪方面考虑,我们都是需要用三个指针实现的, 如下图所示:
文章图片
但是这里其实 n3 指针是需要做判断的,如果 n3 节点为空的话,是不能继续往后移动的。然后当 n2 节点表示的位置为空时,此时 n1 节点就是最后的新链表的头节点,如下图所示:
文章图片
我们看到,此时 n1 即表示反转之后的新链表的头节点。
代码实现
struct ListNode* reverseList(struct ListNode* head){
struct ListNode*n1=NULL;
struct ListNode*n2=head;
if(head==NULL)
return NULL;
struct ListNode*n3=head->next;
while(n2)
{
//核心
n2->next=n1;
//移动
n1=n2;
n2=n3;
if(n3)
n3=n3->next;
}
return n1;
}
好的,那么本文到此就结束啦!如有问题,还请指正呀!
【数据结构|LeetCode(206. 反转链表)】
文章图片
推荐阅读
- C语言|C语言项目实践——通讯录(三版本联合分解)
- 小项目集合|基于C语言扫雷游戏的设计与实现
- 错题锦集|C语言错题锦集(持续更新)
- 云原生|什么是云原生(——软件开发的现代方法)
- 算法训练(C语言版本)|112. 路径总和
- 二叉树(Binary|LeetCode 337. House Robber III - 二叉树系列题25
- 小项目集合|C语言小项目——通讯录(适合刚学完C语言的初学者)
- LeetCode|【每日一题】——合并区间
- LeetCode|【每日一题】——单调递增的数字