算法-链表反转操作

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

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,本节,...

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

通过分析LinkedHashMap了解LRU

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

733
来自专栏Code_iOS

数据结构:集合

工程代码 Github: Data_Structures_C_Implemention -- Set

1503
来自专栏恰同学骚年

数据结构基础温故-4.树与二叉树(下)

上面两篇我们了解了树的基本概念以及二叉树的遍历算法,还对二叉查找树进行了模拟实现。数学表达式求值是程序设计语言编译中的一个基本问题,表达式求值是栈应用的一个典型...

892
来自专栏后端之路

优先级队列之PriorityQueue

背景 前面几篇的队列基本都是和插入顺序相关的,一般来说可以先进先出,当然也可以通过双向队列实现进后出等等 那么在开发中还存在如下一些需求 不同的任务过来可以进入...

2967
来自专栏来自地球男人的部落格

[LeetCode] 78. Subsets

【原题】 Given a set of distinct integers, nums, return all possible subsets. Not...

2479
来自专栏mathor

Map

1264
来自专栏有趣的Python

算法与数据结构(五)二叉搜索树

二叉搜索树 (Binary Search Tree) 核心是解决问题。高效解决问题。 查找问题 Searching Problem: 查找问题是计算机中非常重...

2916
来自专栏Java爬坑系列

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

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

832
来自专栏武培轩的专栏

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

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

3387

扫码关注云+社区