摘要:扯淡之前听说过面试反转链表的梗,也尝试着自己实现了一次,算是比较简单的问题。当然,前提是我们只持有头节点的引用,且称为,那么链表反转后的头节点,就是。
扯淡
之前听说过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
摘要:假设反转对象节点为,反转指向的结点为,反转后指向的结点为首结点。当然也可以根据栈先进后出的特点,使用栈反转链表。 ⭐️前面的话⭐️ 大家好!博主开辟了一个新的专栏—...
摘要:算法思路两种方法一般反转递归法一般解决定义三个指针,分别为,存储当前结点,指向反转好的结点的头结点,存储下一结点信息。递归法重点分析先确定终止条件当下一结点为时,返回当前节点判断当前的链表是否为递归找到尾结点,将其存储为头结点。 Time:2019/4/23Title: Reverse Linked ListDifficulty: EasyAuthor: 小鹿 题目:Reverse...
摘要:今天来将一下面试中经常问到的一个问题链表反转。题目给一个单向链表,请编写一个函数,把链表反转,并把反转的链表返回。假设给的节点为双向链表反转函数如下 今天来将一下面试中经常问到的一个问题:链表反转。 【题目1】给一个单向链表,请编写一个函数,把链表反转,并把反转的链表返回。 假设给的节点为 class ListNode{ int val; ListNode next; ...
摘要:示例输入输出进阶你可以迭代或递归地反转链表。可以设置一个指针,指向,保证后续的操作然后将,往前挪动,当然还有,直到为空,这时指向反转后链表的头结点。接下来考虑递归结束的条件非常显然,子链表只有一个节点是递归结束,直接返回该节点。 本文来自 SoulOH 的CSDN 博客 ,原文地址请点击:https://blog.csdn.net/SoulOH/... 题目:反转一个单链表。 示例: ...
阅读 4595·2021-11-18 13:23
阅读 865·2021-09-22 15:24
阅读 1877·2021-09-06 15:00
阅读 2587·2021-09-03 10:30
阅读 1242·2021-09-02 15:15
阅读 2020·2019-08-30 15:54
阅读 2988·2019-08-30 15:44
阅读 1415·2019-08-29 15:12