Java数据结构之单链表反转

    选择打赏方式

今天早上我被一个单链表反转题目给难到了,这是曾经腾讯的面试题,说实话大厂的面试题真的有点难度,不过相对来说这应该是面试题中比较简单的了,但是就是这个题,我想了半小时才搞清楚,不过我才开始学习数据结构,到以后题目做多了,应该会好很多吧!

题目

就是单链表反转,给定一个链表,将其倒着输出

思路分析

单链表是靠内部的指针将数据一个一个串联起来的,如果其中某一个指针断了,那么整个链表将不存在,所以头部指针是不能动的,有一种思路,创建一个temp,遍历整个链表,将遍历到的每一个数据都放在新链表的第一个位置,再将他们连接起来,最后再将头部指针与这个新链表连接起来,题目得解

代码实现

  1. 创建一个新的头指针(headReversal),区别于已经存在的头指针
  2. 创建一个temp遍历整个链表
  3. 创建一个next保存temp的下一个数据(因为temp是我们需要取出来的数据,取出来之后从那个地方开始链表就断开了,如果不能保存temp的下一个数据,那么将永远找不到temp接下来的数据
    public void ListReversal(){
        Person headRever = new Person(0,"",0);
        Person next = null;
        Person temp = head.next;
        //判断当前链表状态,如果为空,或者只有一个数据,则直接结束程序
        if(temp == null || temp.next == null){
            return;
        }
        //遍历的条件是链表不为空
        while(temp !=null){
        //保存temp的下一个数据
            next = temp.next;
        //将temp指向新的头结点的下一个数据,如果是第一次指向那么将为null,因为此时头结点没有指向任何数据
            temp.next = headReversal.next;
        //将头结点指向temp
            headReversal.next = temp;
            temp = next;
        }
        //最后将头指针指向新的链表
        head.next = headReversal.next;
    }

确实有一点难理解,特别是temp.next = headReversal.next;这一句,但是画一张图,多想几遍,还是能理解的,如果不理解就多想几遍,我想即使这样的题有难度,但是这才是最好的

版权声明:若无特殊注明,本文为《若离风》原创,转载请保留文章出处。
本文链接:https://www.rlfit.cn/post-54.html
正文到此结束

热门推荐

发表吐槽

你肿么看?

你还可以输入 250 / 250 个字

嘻嘻 大笑 可怜 吃惊 害羞 调皮 鄙视 示爱 大哭 开心 偷笑 嘘 奸笑 委屈 抱抱 愤怒 思考 日了狗 胜利 不高兴 阴险 乖 酷 滑稽

评论信息框
可使用QQ号实时获取昵称+头像

私密评论

吃奶的力气提交吐槽中...


既然没有吐槽,那就赶紧抢沙发吧!