开发者社区> yexx> 正文

【算法】Java单链表逆转

简介: 单链表逆转置的递归与非递归方式 Node类 public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } 先看递归求解: public ListNode reverse1(ListNode head) {
+关注继续查看

单链表逆转置的递归与非递归方式

Node类

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

先看递归求解:

public ListNode reverse1(ListNode head) {
        // 当为空或者本节点为末尾节点的时候
        if (head == null || head.next == null)
            return head;
        ListNode temp = head.next;
        ListNode reversedHead = reverse1(head.next);
        // 获取先前的下一个节点,让该节点指向自身
        temp.next = head;
        // 破坏以前自己指向下一个节点
        head.next = null;
        // 层层传递给最上面的
        return reversedHead;
    }

有点难理解,看看debug的图基本上就能懂了。
这里写图片描述

就是在temp存储了尾节点,然后再一层层往前。这个head.next=null是必须的,因为最后一个节点时不会自己赋值的,会形成一个环。

非递归算法:

public ListNode reverse(ListNode head){  
        ListNode p = head,q = null,front = null;  
        while(p!=null){  
            q = p.next;//设置q是p结点的后继结点,即用q来保持p的后继结点  
            p.next = front;//逆转,即使p.next指向p结点的前驱结点  
            front = p;//front向后移一步  
            p = q;//p向后移一步  
        }  
        head = front;//head指向原链表的最后一个结点,完成逆转  
        return head;
   }  

这个理解起来就比较简单啦。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Java算法基础 - 单链表详解(文末有配套视频)
咳咳,我是小白,没错,主线剧情又回来了。现在我遇到麻烦了,老板要我设计一个类,可以用来保存多个客户的资料。
20 0
【Java基础】 建立一个单链表(增删查改)
链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
22 0
《Java数据结构基础》单链表的手动实现
《Java数据结构基础》单链表的手动实现
15 0
【Java数据结构】实现单链表
【Java数据结构】实现单链表
23 0
Java单链表的应用实例
Java单链表的应用实例
24 0
Java数据结构之单链表(配图详解,简单易懂)
链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的,看着这段文字抽象不,生硬不(本笔记主要介绍单向不带头节点非循环链表)
41 0
java语言实现单链表---不含头结点
java实现单链表—含头结点,且该篇文章与另一篇含头结点的实现单链表的文章第一部分均是重复的,若看可忽略,说到这里必须要写下含不含头结点的区别,带有头结点是为了更好的实现单链表的功能,带有头结实现的insert、remove等方法相比于不带头结点的单链表会更简洁一些,此外,学习不带头结点的和带有头结点的单链表是没有区别的。
22 0
java语言实现单链表--含头结点
线性表是我们最常用的一种数据结构,线性表包含顺序表和链表,顺序表典型应用就是我们常用的ArrayList,链表的典型应用其中就有我们常用的LinkedList。LinkedList他的底层就是使用链表来存储数据元素的。这篇文章用以总结单链表的实现以及使用并且对比单链表与顺序表的优缺点,确定其使用功能场景。
36 0
单链表的基本操作(Java实现)
单链表的基本操作(Java实现)
83 0
通用版!完整代码,单链表SingleLinkedList增删改查,反转,逆序,有效数据等Java实现
通用版!完整代码,单链表SingleLinkedList增删改查,反转,逆序,有效数据等Java实现
36 0
+关注
yexx
CSDN博客地址---http://blog.csdn.net/bug_moving GitHub地址---https://github.com/androidwolf
文章
问答
视频
文章排行榜
最热
最新
相关课程
更多
相关电子书
更多
JAVA开发手册1.5.0
立即下载
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
相关实验场景
更多