算法-链表反转操作

题目: 定义一个函数,输入一个链表的头结点,反转该链表并输出反转后的头结点。链表定义如下:

struct ListNode
{
  int value;
  ListNode *next;
};

解题思路:

原本我们有一个这样的链表,并且知道他的头结点,即存放数值1的节点的地址。

链表反转后的效果:

并返回新的链表的头结点,即原链表最后一个结点的地址。 为了现实上面的功能,需要调整原链表中的指针方向,即本来结点2的next要指向结点3的地址,现在将其指向结点1的地址。要完成这个工作需要两个指针,一个指针* pNode指向当前遍历到的结点,一个指针* pPrev指向它前一个结点。

那么遍历到结点2时,就像这样:

此时就出现一个问题,链表已经断开了,在原链表中结点2后面的结点是哪个就不知道了(因为* next已经指向了结点1),为了避免这个问题,我们需要定义第三个指针* pNext,用来指向当前的结点的下一个结点。

剩下的工作就是遍历原链表,然后调整指针的指向,但是循环总需要一个退出条件,这个条件就是原链表的最后一个结点的* pNext = null

代码实现:

ListNode * ReverseList(ListNode * pHead)
{
    ListNode * pRevesedHead = nullptr;//翻转后的头结点
    ListNode * pNode = pHead;//指向当前结点的指针
    ListNode * pPrev = nullptr;//指向当前结点的前一个结点的指针
    while (pNode != nullptr)//遍历原链表
    {
        ListNode * pNext = pNode->next;//定义指向当前结点下一个结点的指针并赋值
        if (pNext == nullptr)//只有一个结点的情况或者到达原链表的最后一个结点
        {
            pRevesedHead = pNode;//返回
        }
        pNode->next = pPrev;//当前结点的next指向pPrev
        //对pPrev重新赋值,这是因为第一次遍历链表时pPrev一定为null,但是随着遍历
        //pPrev的值总需要跟着变化,相对于下一个结点而言的前一个结点就是当前的结点(有点绕)
        pPrev = pNode;
        //和前面一行是一样的道理,pNode永远只指向当前的结点,但是在遍历的过程中,当前的结点
        //总要一直在向后移动(要不遍历什么呢),所以后移的结点就是pNext,就像之前说的,pNext
        //是预先保存下来的原链表的下一个结点,因为当我们执行pNode->next = pPrev链表就已经断开了
        pNode = pNext;
    }
    return pRevesedHead;
}

额,注释越加越多,要解释明白这个简短的代码也是挺麻烦的,也说明了这个代码的质量确实很高,再贴一些图说明下吧。

最后需要注意的是while里面的if判断,它有两个作用:

1 如果原链表只有一个结点的,那么直接把这个结点地址给预先定义好的反转后链表的头结点。

2 如果原链表不只有一个结点,最终也要进入if,因为遍历总有结束的时候,这时进入if后会紧跟着退出while。

测试的程序就不贴了,本来这就是个很常见的面试题,有很多资料可以找到完整的测试例程,而且自己写一个也不麻烦,在上面只是说下自己的理解。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏诸葛青云的专栏

学习心得:C语言实现链表的操作超详细

今天将给大家讲述链表的学习心得。学习数据结构,毋庸置疑链表必须学好,后面的栈、队列、树、图都是以链表为基础的;链表的种类很多,有单链表、双链表、循环链表、非循环...

250
来自专栏好好学java的技术栈

“365算法每日学计划”:04打卡-自己动手写一个单链表

1193
来自专栏恰同学骚年

剑指Offer面试题:14.链表的倒数第k个节点

PS:这是一道出境率极高的题目,记得去年参加校园招聘时我看到了3次,但是每次写的都不完善。

704
来自专栏算法与数据结构

数据结构 单链表&顺序表

顺序表: 一般使用数组(C语言中的数组采用顺序存储方式。即连续地址存储)来描述。 优点:在于随机访问元素, 缺点:插入和和删除的时候,需要移动大量的元素。 链表...

3209
来自专栏恰同学骚年

剑指Offer面试题:15.反转链表

  由于题目并没有要求必须原地反转,因此可以借助外部空间实现。这里可以将单链表储存为数组,然后按照数组的索引逆序进行反转。但是,此方式比较浪费空间,而且需要两次...

782
来自专栏小詹同学

Leetcode打卡 | No.21 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

791
来自专栏后台开发+音视频+ffmpeg

redis跳跃表源码详解

跳跃表是一种有序的数据结构,他通过在每个节点中维护多个指向其它节点的指针,从而达到快速访问节点的目的。跳跃表的查找操作平均时间复杂度为o(logN)。在大部分情...

1115
来自专栏我的技术专栏

数据结构图文解析之:二叉堆详解及C++模板实现

1024
来自专栏mathor

LeetCode164. 最大间距

 这道题用到了桶排序的思想,但是跟排序没啥关系,思路是这样的,数组中有n个元素,那么就构建n+1个桶,桶的属性有三个,最大值最小值以及是否为空。桶的下标从0...

412
来自专栏marsggbo

常见排序算法-Python实现

常见排序算法-Python实现 python 排序 算法 1.二分法 python    32行 #coding=utf-8 def binary_s...

1819

扫码关注云+社区