算法-链表反转操作

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

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 条评论
登录 后参与评论

相关文章

来自专栏Linyb极客之路

简洁又快速地处理集合——Java8 Stream(下)

而 parallelStream() 是并行流方法,能够让数据集执行并行操作,后面会更详细地讲解

1.1K3
来自专栏郭耀华‘s Blog

《剑指offer》全部题目-含Java实现

陆续刷了好久,算是刷完了《剑指offer》,以下全部AC代码,不一定性能最优,如有错误或更好解答,请留言区指出,大家共同交流,谢谢~ 1.二维数组中的查找 在...

6057
来自专栏Java技术

在Java中如何高效判断数组中是否包含某个元素

原文地址:http://www.hollischuang.com/archives/1269

761
来自专栏小二的折腾日记

剑指offer-刷题总结

分析:由于每一行都有递增的特性,我们可以采用类似二分搜索的方法。将数组分成行列来进行搜索。

3482
来自专栏深度学习与计算机视觉

算法-O(1)时间删除链表的指定结点

题目:给定一个链表的头指针和一个结点的指针,定义一个函数在O(1)时间删除该结点。链表结点与函数的定义如下: struct ListNode { int v...

1907
来自专栏Duncan's Blog

Hive SQL 学习

example: 一个班有学生id,成绩,班级,现在将学生根据班级按照成绩排名。(partition by)

902
来自专栏猿人谷

查找链表中倒数第k个结点

题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。链表结点定义如下: struct ListNode { in...

1945
来自专栏于晓飞的专栏

读 Java TimSort算法 源码 笔记

本来准备看Java容器源码的。但是看到一开始发现Arrays这个类我不是很熟,就顺便把Arrays这个类给看了。Arrays类没有什么架构与难点,但Arrays...

742
来自专栏郭耀华‘s Blog

剑指offer 第十一天

46.扑克牌顺子 LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自...

3099
来自专栏高性能服务器开发

(三)dict哈希结构3

/* This function performs just a step of rehashing, and only if there are * no...

2628

扫码关注云+社区