资讯专栏INFORMATION COLUMN

反转链表

20171112 / 1447人阅读

摘要:扯淡之前听说过面试反转链表的梗,也尝试着自己实现了一次,算是比较简单的问题。当然,前提是我们只持有头节点的引用,且称为,那么链表反转后的头节点,就是。

扯淡

之前听说过google面试反转链表的梗,也尝试着自己实现了一次,算是比较简单的问题。但在纸上手写代码的时候,思维就很乱,可能是隔的时间长忘记了,或者之前就跟本没有理清思路,所以被虐的很惨。
这篇文章的目的就是梳理一下思路,加深印象。如果有更好的算法,留言求虐啊~

描述

这是一个普通的链表,由ABCD4个节点组成,每个节点都包含数据区-data和指向下一个节点的引用-next

反转链表,顾名思义就是将链表每个节点的next引用反过来,如ABCD,变为DCBA。当然,前提是我们只持有头节点的引用,且称为Node a,那么链表反转后的头节点,就是Node d。

分析

要将此链表反转,我们核心的需求是:修改每一个节点的next引用,将next指向前一个节点,将原来的头节点A中的next,指向null

既然每一个节点都需要操作,那就考虑循环吧,设一个索引(或者称为游标)node(可以利用节点A的引用),从节点A跑到节点D,当它再往后移动指向null时,循环结束。那么循环边界条件则为

while(node != null){
//do something
}

然后我们再看看每个节点做一次反转(即每次循环),都需要做什么事情

在修改当前节点的next引用之前,要先保存其值,为了避免丢失下一个节点(即Node next)的引用。

进行反转,修改当前节点的next,使之指向上一个节点(即Node last

要保存当前节点的引用,为了提供给下一次循环时,对下个节点进行反转

为了保证while循环可以从头节点A遍历到尾节点D,那么游标node在循环体最后要向后移动一个节点,即指向下一个节点。

代码
Node reversalLinkedList(Node node){
    Node last = null;
    Node next = null;
    while(node != null){
        next = node.getNext();//1 拿到下个节点的引用,为了提供给第4步使node向链表后方移动
        node.setNext(last);//2 将当前节点指向上一个节点
        last = node;//3 将last指向当前节点,提供给下次循环的第2步
        node = next;//4 将当前节点的引用(即游标)指向下一个节点        
    }
    /*
    * 循环完成后,node和next都指向了原节点D的next指向的位置,即null
    * 而last指向了上述null前面的位置,即节点D
    * 将last返回,则得到链表ABCD反转后链表DCBA的头节点D
    */
    return last;
}

逻辑其实很简单,需要注意的就是每次循环时需要暂存的引用 -- next,last

图解

每次循环其实就是修改当前节点next的引用+三个引用(last,node,next)的后移,如下图

第一次循环前

第一次循环的过程

第一次循环结束后

最后全部反转后

总结

保存当前节点,上一个节点,下一个节点的引用

每次循环最后,当前节点向后移动

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/65550.html

相关文章

  • 剑指offer系列——剑指 Offer 24. 反转链表(C语言)

    摘要:假设反转对象节点为,反转指向的结点为,反转后指向的结点为首结点。当然也可以根据栈先进后出的特点,使用栈反转链表。 ⭐️前面的话⭐️ 大家好!博主开辟了一个新的专栏—...

    weakish 评论0 收藏0
  • LeetCode 之 JavaScript 解答第206题 —— 反转链表(Reverse Link

    摘要:算法思路两种方法一般反转递归法一般解决定义三个指针,分别为,存储当前结点,指向反转好的结点的头结点,存储下一结点信息。递归法重点分析先确定终止条件当下一结点为时,返回当前节点判断当前的链表是否为递归找到尾结点,将其存储为头结点。 Time:2019/4/23Title: Reverse Linked ListDifficulty: EasyAuthor: 小鹿 题目:Reverse...

    zhangfaliang 评论0 收藏0
  • 【面试算法】链表反转

    摘要:今天来将一下面试中经常问到的一个问题链表反转。题目给一个单向链表,请编写一个函数,把链表反转,并把反转的链表返回。假设给的节点为双向链表反转函数如下 今天来将一下面试中经常问到的一个问题:链表反转。 【题目1】给一个单向链表,请编写一个函数,把链表反转,并把反转的链表返回。 假设给的节点为 class ListNode{ int val; ListNode next; ...

    adam1q84 评论0 收藏0
  • LeetCode:206. 反转链表

    摘要:示例输入输出进阶你可以迭代或递归地反转链表。可以设置一个指针,指向,保证后续的操作然后将,往前挪动,当然还有,直到为空,这时指向反转后链表的头结点。接下来考虑递归结束的条件非常显然,子链表只有一个节点是递归结束,直接返回该节点。 本文来自 SoulOH 的CSDN 博客 ,原文地址请点击:https://blog.csdn.net/SoulOH/... 题目:反转一个单链表。 示例: ...

    wenshi11019 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<