【算】链表反转

1treeS 发布于2019-08-16 14:00 / 1025人阅读

摘要：问题最近研究算法，遇到的一道很有意思的问题怎么把一个链表反转很容易想到一个方法遍历链表，数组作栈存储路径，元素逐个出栈得到的就是反转后的链表查找资料发现，有更好的方式实现。老规矩，完整代码见暗夜君王的练习链表反转

问题

最近研究算法，遇到的一道很有意思的问题——怎么把一个链表反转？
很容易想到一个方法：遍历链表，数组作栈存储路径，元素逐个出栈得到的就是反转后的链表！查找资料发现，有更好的方式实现。

仔细研究后，终于明白了其中的奥妙。小僧掌握了两种方法，以下分别进行说明。

首先给出链表结构：

public class LinkedNode {
    Integer id ;
    LinkedNode next;
    
    public LinkedNode(Integer id) {
        this.id = id;
    }
}

下一步构造出上图的链表结构：

LinkedNode node1 = new LinkedNode(1);
LinkedNode node2 = new LinkedNode(2);
LinkedNode node3 = new LinkedNode(3);
LinkedNode node4 = new LinkedNode(4);
node1.next = node2;
node2.next = node3;
node3.next = node4;

双指针遍历法

先给出代码实现：

/**
 * 链表翻转，循环 + 双指针（pre、next）实现
 * @param cur
 * @return
 */
public LinkedNode reverse(LinkedNode cur){
    LinkedNode pre = null;

    while (cur!=null){
        LinkedNode next = cur.next; // 1.
        cur.next = pre; // 2.
        pre = cur;  // 3.
        cur = next; // 4.
    }

    return pre;
}

循环体之前，链表示意图：

之后进入while循环，注释标注的四个步骤会产生如下变化（图中编号与注释编号一一对应）：

第一次循环后，链表变成这样：

之后的遍历，链表的变化示意：

可见，while循环执行完，pre指向的节点，已经是最新的头节点了！

递归法

递归的实现方式，似乎更容易理解。

/**
 * 链表反转，递归实现
 * @param node
 * @return
 */
public LinkedNode reverse2(LinkedNode node){
    if(node.next==null){
        return node;
    }

    LinkedNode newHead = reverse2(node.next);
    node.next.next = node;  //node.next.next 换成 newHead.next 不行，因为node在递归中在追溯上一个节点，仔细体会下
    node.next = null;
    return newHead;
}

首先会通过递归调用找到尾节点，之后做了两件事：

尾节点反指 (node.next.next = node;)

当前节点指向null节点 (node.next = null;)

rentun newHead后，回溯到节点2（此时node就是节点2），再次重复之前的两件事——节点反指和当前节点指向null节点。

再次回溯，得到最终的结果。

老规矩，完整代码见git：暗夜君王的demo练习——链表反转

Done !

云服务器 GPU云服务器 python反转链表反转函数反转数组反转

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

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

＜LeetCode天梯＞Day026 反转链表（递归法+（迭代法）双链表法） | 初级算法 | Py

摘要：关于递归这里提一两点递归基本有这几步递归的模板，终止条件，递归调用，逻辑处理。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无所住而生...

imingyu 2021-11-17 09:33 评论0 收藏0
为什么你学不会递归？刷题几个月，告别递归，谈谈我的经验

摘要：第一递归函数功能假设的功能是求第项的值，代码如下找出递归结束的条件显然，当或者我们可以轻易着知道结果。定义递归函数功能假设函数的功能是反转但链表，其中表示链表的头节点。可能很多人在大一的时候，就已经接触了递归了，不过，我敢保证很多人初学者刚开始接触递归的时候，是一脸懵逼的，我当初也是，给我的感觉就是，递归太神奇了！可能也有一大部分人知道递归，也能看的懂递归，但在实际做题过程中，却不知道怎么...

Achilles 2019-05-23 17:29 评论0 收藏0
＜LeetCode天梯＞Day028 回文链表（双指针+递归+栈+数组） | 初级算法 | Pyth

摘要：先实现栈操作遍历链表，把每个节点都进中然后再遍历链表，同时节点依次出栈，二者进行比较。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无...

miguel.jiang 2021-11-19 09:40 评论0 收藏0