文档章节

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

leopardlz
 leopardlz
发布于 2017/08/16 09:59
字数 420
阅读 23
收藏 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科技大本营
09/27
0
0
算法和编程面试题精选 TOP50!(附代码+解题思路+答案)

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

CSDN资讯
10/02
0
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
07/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Redis分布式锁的实现原理看这篇就够了~

一、写在前面 现在面试,一般都会聊聊分布式系统这块的东西。通常面试官都会从服务框架(Spring Cloud、Dubbo)聊起,一路聊到分布式事务、分布式锁、ZooKeeper等知识。 所以咱们这篇文章就来...

Java干货分享
11分钟前
1
0
Actor并发编程模型浅析

一.Actor模型介绍 在单核 CPU 发展已经达到一个瓶颈的今天,要增加硬件的速度更多的是增加 CPU 核的数目。而针对这种情况,要使我们的程序运行效率提高,那么也应该从并发方面入手。传统的多...

终日而思一
11分钟前
1
0
利用arthas实时定位线上性能问题

0. 场景及需求 我们线上5台solr读服务器,配置一样,但是相同的请求,其中一台响应时间明显比其他4台慢,我们想通过arthas来定位具体哪里执行慢。 1. arthas介绍 阿里开源的java调试工具,能...

andersChow
13分钟前
2
0
docker 启动策略

Docker run的时候使用--restart参数 no - Container不重启 on-failure - container推出状态非0时重启 always - 始终重启 例如: docker run --restart=always -itd -p 2222:22 -p 3306:3306......

colin_86
13分钟前
1
0
Thinkphp5开发OA办公系统之招聘申请

开发运行环境: 神舟笔记本K650D-G6D1 i5-6400 GTX950M Windows 10 专业版 Nginx 或 Apache Web 服务器软件 MySQL5.7.x 数据库 PHP7.1.0 PHPStrom 2017 PowerDesigner 16.5 Axure RP8 原型设......

乐兔CRM
15分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部