文档章节

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

leopardlz
 leopardlz
发布于 2017/08/16 09:59
字数 420
阅读 24
收藏 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
西青
程序员
私信 提问
算法和编程面试题精选TOP50!(附代码+解题思路+答案)

作者 | javinpaul 编译 | 王天宇、Jane 整理 | Jane 出品 | AI科技大本营 【导读】之前我们给同学们推荐了很多关于 Python 的面试资源,大家都表示很有用。这次营长表示要翻 Java 的牌子啦~...

AI科技大本营
2018/09/27
0
0
算法和编程面试题精选 TOP50!(附代码+解题思路+答案)

作者 | javinpaul 出品 | AI科技大本营 数组 数组,将元素存储到内存的连续位置中,是最基本的数据结构。在任何和编程相关的面试中,都会被问到和数组相关的问题,可以说是非常热门的考题之一...

CSDN资讯
2018/10/02
0
0
143. Reorder List - LeetCode

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

yysue
2018/07/15
0
0
为工程师准备的 50 道数据结构和算法面试题

已有许多计算机科学专业的毕业生和程序员在 Uber 和 Netflix 等初创公司、亚马逊,微软和谷歌等大型组织,以及诸如 Infosys 或 Luxsoft 这样的服务型公司中申请过编程、编码及软件开发职位,...

oschina
2018/12/19
0
0
LeetCode算法题-Palindrome Linked List(Java实现)

这是悦乐书的第196次更新,第202篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第58题(顺位题号是234)。给出一个单链表,确定它是否是回文。例如: 输入:1-> 2 输出:fal...

小川94
2018/12/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周一乱弹 —— 白掌柜说了卖货不卖身

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @爱漫爱 :这是一场修行分享羽肿的单曲《Moony》 手机党少年们想听歌,请使劲儿戳(这里) @clouddyy :开不开心? 开心呀, 我又不爱睡懒觉…...

小小编辑
今天
8
0
大数据教程(11.7)hadoop2.9.1平台上仓库工具hive1.2.2搭建

上一篇文章介绍了hive2.3.4的搭建,然而这个版本已经不能稳定的支持mapreduce程序。本篇博主将分享hive1.2.2工具搭建全过程。先说明:本节就直接在上一节的hadoop环境中搭建了! 一、下载apa...

em_aaron
今天
3
0
开始看《JSP&Servlet学习笔记》

1:WEB应用简介。其中1.2.1对Web容器的工作流程写得不错 2:编写Servlet。搞清楚了Java的Web目录结构,以及Web.xml的一些配置作用。特别是讲了@WebServlet标签 3:请求与响应。更细致的讲了从...

max佩恩
今天
4
0
mysql分区功能详细介绍,以及实例

一,什么是数据库分区 前段时间写过一篇关于mysql分表的的文章,下面来说一下什么是数据库分区,以mysql为例。mysql数据库中的数据是以文件的形势存在磁盘上的,默认放在/mysql/data下面(可...

吴伟祥
今天
3
0
SQL语句查询

1.1 排序 通过order by语句,可以将查询出的结果进行排序。放置在select语句的最后。 格式: SELECT * FROM 表名 ORDER BY 排序字段ASC|DESC; ASC 升序 (默认) DESC 降序 1.查询所有商品信息,...

stars永恒
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部