反转链表

20171112 发布于2019-08-14 15:16 / 1389人阅读

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

扯淡

之前听说过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)的后移，如下图

第一次循环前

第一次循环的过程

第一次循环结束后

最后全部反转后

总结

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

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

服务器托管海外云主机 python反转链表反转函数反转数组反转

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

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

剑指offer系列——剑指 Offer 24. 反转链表（C语言）

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

weakish 2021-09-03 10:29 评论0 收藏0
LeetCode 之 JavaScript 解答第206题 —— 反转链表（Reverse Link

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

zhangfaliang 2019-08-23 17:12 评论0 收藏0
【面试算法】链表反转

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

adam1q84 2019-08-14 15:19 评论0 收藏0
LeetCode：206. 反转链表

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

wenshi11019 2019-08-23 12:08 评论0 收藏0