算法-链表反转操作

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

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

相关文章

来自专栏老马说编程

(41) 剖析HashSet / 计算机程序的思维逻辑

查看历史文章,请点击上方链接关注公众号。 上节介绍了HashMap,提到了Set接口,Map接口的两个方法keySet和entrySet返回的都是Set,本节,...

19590
来自专栏Bingo的深度学习杂货店

Q101 Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric aroun...

33980
来自专栏用户3030674的专栏

Java 工具类—日期获得,随机数,系统命令,数据类型转换

15610
来自专栏cmazxiaoma的架构师之路

通过分析LinkedHashMap了解LRU

我们都知道LRU是最近最少使用,根据数据的历史访问记录来进行淘汰数据的。其核心思想是如果数据最近被访问过,那么将来访问的几率也更高。在这里提一下,Redis缓存...

17430
来自专栏mathor

Map

15840
来自专栏用户画像

7.7.5 最佳归并树

文件经过置换-选择排序之后,得到的是长度不等的初始归并段。下面讨论如何组织初始归并段的归并顺序,使I/O访问次数最少。

9510
来自专栏JAVA高级架构

Java数据结构与算法解析——2-3树

二叉查找树对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率,...

42270
来自专栏Java爬坑系列

【Java入门提高篇】Day28 Java容器类详解(十)LinkedHashMap详解

  今天来介绍一下容器类中的另一个哈希表———》LinkedHashMap。这是HashMap的关门弟子,直接继承了HashMap的衣钵,所以拥有HashMap...

9320
来自专栏郭耀华‘s Blog

剑指offer 第十一天

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

34790
来自专栏武培轩的专栏

Java中Set集合是如何实现添加元素保证不重复的?

Java中Set集合是如何实现添加元素保证不重复的? Set集合是一个无序的不可以重复的集合。今天来看一下为什么不可以重复。 Set是一个接口,最常用的实现类就...

41270

扫码关注云+社区

领取腾讯云代金券