文档章节

java实现数组转链表、链表按指定起始位置反转,链表反转

leopardlz
 leopardlz
发布于 2017/08/16 09:59
字数 420
阅读 11
收藏 0
点赞 0
评论 0

package com.lz.blade.offer;

/**
 * <p>
 * 链表相关操作
 * </p>
 *
 * @author ZLi 2017-8-16
 *
 */
public class ReverChain {

    public static void main(String[] args) {
        int[] array = { 1, 2, 3, 4, 5, 6, 7 };
        Node head = transfer(array);
        System.out.println("反转前:");
        Node node = head;
        while (node != null) {
            System.out.println(node.getVal());
            node = node.getNext();
        }
        System.out.println("反转后:");
        Node node0 = reverse(head, 3);
        while (node0 != null) {
            System.out.println(node0.getVal());
            node0 = node0.getNext();
        }
    }

    /**
     * 链表逆序打印
     *
     * @param head
     */
    public static void reverse0(Node head) {
        if (head.next == null) {
            System.out.println(head.val);
            return;
        }
        Node next = head.getNext();
        head.setNext(null);
        reverse0(next);
        System.out.println(head.val);
    }

    /**
     * 按指定位置逆序
     *
     * @param head
     * @param from
     * @param to
     * @return
     */
    public static Node reverse(Node head, int from, int to) {
        if (head == null || head.next == null || from > to) {
            return head;
        }
        Node next = null;
        Node res = null;
        int i = 0;
        Node pre = null;
        Node preTail = null;
        Node middle = null;
        while (head != null) {
            if (i < from - 1) {
                if (pre == null) {
                    pre = preTail = new Node(head.val);
                } else {
                    preTail.next = new Node(head.val);
                    preTail = preTail.next;
                }
                head = head.next;
            }
            if (i >= from - 1 && i < to) {

                next = head.next;
                if (middle == null) {
                    res = middle = new Node(head.val);
                } else {
                    head.next = res;
                    res = head;
                }
                head = next;
            }
            if (i >= to) {
                break;
            }
            i++;
        }
        middle.next = next;
        preTail.next = res;
        return pre;
    }

    /**
     * 链表按指定数字逆序
     *
     * @param head
     * @return
     */
    public static Node reverse(Node head, int num) {
        if (head.next == null || head == null) {
            return head;
        }
        Node next = null;
        Node res = null;
        int i = 0;
        Node tail = null;
        while (i < num) {
            next = head.next;
            if (res == null) {
                res = tail = new Node(head.val);
            } else {
                head.next = res;
                res = head;
            }
            head = next;
            i++;
        }
        tail.next = next;
        return res;
    }

    /**
     * 把数组转换成链表
     *
     * @param array
     * @return
     */
    public static Node transfer(int[] array) {
        if (array == null) {
            return null;
        }
        Node head = null;
        Node tail = null;
        for (int i = 0; i < array.length; i++) {
            if (head == null) {
                tail = new Node(array[i]);
                head = tail;
            } else {
                tail.next = new Node(array[i]);
                tail = tail.next;
            }
            tail.next = null;
        }
        return head;
    }

    /**
     * 非递归
     *
     * @param cur
     * @return
     */
    public static Node noRecursionReverse(Node cur) {
        if (cur == null) {
            return null;
        }
        Node pre = null;
        Node next = null;
        while (cur != null) {
            next = cur.getNext();
            cur.setNext(pre);
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 递归实现
     *
     * @param head
     * @return
     */
    public static Node recursionReverse(Node head) {
        if (head == null || head.getNext() == null) {
            return head;
        }
        Node next = head.getNext();
        head.setNext(null);
        Node reverseNode = recursionReverse(next);
        next.setNext(head);
        return reverseNode;
    }
}

 

© 著作权归作者所有

共有 人打赏支持
leopardlz
粉丝 0
博文 40
码字总数 4393
作品 0
西青
程序员
143. Reorder List - LeetCode

Question 143. Reorder List Solution 题目大意:给一个链表,将这个列表分成前后两部分,后半部分反转,再将这两分链表的节点交替连接成一个新的链表 思路 :先将链表分成前后两部分,将后部...

yysue
07/15
0
0
如何检查一个单向链表上是否有环?

1, 最简单的方法, 用一个指针遍历链表, 每遇到一个节点就把他的内存地址(java中可以用object.hashcode())做为key放在一个hashtable中. 这样当hashtable中出现重复key的时候说明此链表上有环....

NineRec
2014/08/29
0
0
206. Reverse Linked List - LeetCode

Question 206. Reverse Linked List Solution 题目大意:对一个链表进行反转 思路: Java实现:

yysue
前天
0
0
JDK源码之LinkedList

LinkedList简介 LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 LinkedList 实现 List 接口,能对它进行队列操作。 LinkedList 实...

村长大神
2014/03/27
0
0
java简单算法总结

1、翻转字符串 function reverseString(str) { }reverseString("hello"); 2、阶乘算法 public static int factorialize(int num) { } else { } } public static void main(String[] args......

晚天吹凉风
2017/12/18
4
0
JAVA 常见的类集之Collection&List&Queue

今天回顾类集的基本内容: (一). 类集 实际上就是一个动态的对象数组,与一般的对象数组不同,类集中的对象内容可以任意扩充。 类集的特征: 1.这种框架是高性能的; 2.框架必须允许不同类型...

木木知南
06/14
0
0
JAVA 持有对象——容器初探

引言 如果一个程序只包含固定数量的且其生命周期都是已知对象,那么这是一个非常简单的程序——《think in java》 了解容器前,先提出一个问题,ArrayList和LinkedList谁的处理速度更快呢? ...

jiangmitiao
2015/08/01
0
2
推荐:并发情况下:Java HashMap 形成死循环的原因

在淘宝内网里看到同事发了贴说了一个CPU被100%的线上故障,并且这个事发生了很多次,原因是在Java语言在并发情况下使用HashMap造成Race Condition,从而导致死循环。这个事情我4、5年前也经历...

码代码的小司机
06/19
0
0
ConcurrentHashMap实现机制

Java 内存模型 由于 ConcurrentHashMap 是建立在 Java 内存模型基础上的,为了更好的理解 ConcurrentHashMap,让我们首先来了解一下 Java 的内存模型。 Java 语言的内存模型由一些规则组成,...

zhangchd
2015/04/28
0
0
Java HashMap的死循环

在淘宝内网里看到同事发了贴说了一个 CPU 被 100% 的线上故障,并且这个事发生了很多次,原因是在 Java 语言在并发情况下使用 HashMap 造成 Race Condition,从而导致死循环。这个事情我4、5...

杭州_周陶忠
2013/09/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

CORS 跨域实践

本文首发于个人微信公众号《andyqian》,期待你的关注~ 前言 系统通常都是由单体应用逐渐演化而来,演化成为前后端分离的分布式应用。在享受分布式系统带来的诸多好处之时,随之而来的也有不...

andyqian
10分钟前
6
0
开源 java CMS - FreeCMS2.8 会员管理

项目地址:http://www.freeteam.cn/ 会员组管理 会员管理 会员管理 从左侧管理菜单点击会员管理进入。 添加会员 在会员列表下方点击“添加”按钮。 填写相关属性后点击“保存”按钮即可。 编...

freeteam
11分钟前
0
0
bboss升级至 v5.0.6.8版本,改善对Elasticsearch SQL 的支持

v5.0.6.8功能改进如下: (1)持久层支持支持Elasticsearch SQL,使用参考文档:玩转Elasticsearch SQL功能 (2)解决持久层/elasticsearch模板变量解析多层级不起作用问题 (3)完善国际化功能 (4...

linux-tao
13分钟前
0
0
扫码二维码跳转到某个网站

添加maven依赖 <dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.0.0</version></dependency><dependency><groupId>com.goog......

gaomq
19分钟前
0
0
Windows平台下搭建Git服务器的图文教程

Git没有客户端服务器端的概念,但是要共享Git仓库,就需要用到SSH协议(FTP , HTTPS , SFTP等协议也能实现Git共享,此文档不讨论),但是SSH有客户端服务器端,所以在windows下的开发要把自己...

MKChan
25分钟前
0
0
告警系统主脚本&告警系统配置文件&告警系统监控项目

20.20 告警系统主脚本 准备工作 定义监控系统的各个目录,然后再去定义主脚本,因为是分布式的,所以需要每一台机器都需要定义,事先创建好各个脚本和各个目录,随后脚本直接拷贝过去即可,然...

影夜Linux
26分钟前
0
0
谈谈神秘的ES6——(一)初识ECMAScript

谈谈神秘的ES6——(一)初识ECMAScript 在《零基础入门JavaScript》我们就说过,ECMAScript是JavaScript的核心,是JavaScript语法和语义的解释器,同时也是一个标准。而ECMAScript标准其实也...

JandenMa
今天
1
0
第16章 Tomcat配置

16.1 Tomcat介绍 ####Tomcat介绍 LNMP架构针对的开发语言是PHP语言,php 是一门开发web程序非常流行的语言,早些年流行的是asp,在Windows平台上运行的一种编程语言,但安全性差,就网站开发...

Linux学习笔记
今天
1
0
流利阅读笔记29-20180718待学习

高等教育未来成谜,前景到底在哪里? Ray 2018-07-18 1.今日导读 在这个信息爆炸的年代,获取知识是一件越来越容易的事情。人们曾经认为,如此的时代进步会给高等教育带来众多便利。但事实的...

aibinxiao
今天
12
0
OSChina 周三乱弹 —— 你被我从 osc 老婆们名单中踢出了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @小鱼丁:分享五月天的单曲《后来的我们 (电影《后来的我们》片名曲)》: 《后来的我们 (电影《后来的我们》片名曲)》- 五月天 手机党少年们想...

小小编辑
今天
810
20

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部