文档章节

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

leopardlz
 leopardlz
发布于 2017/08/16 09:59
字数 420
阅读 19
收藏 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
07/16
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
JDK源码之LinkedList

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

村长大神
2014/03/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

如何通过 J2Cache 实现分布式 session 存储

做 Java Web 开发的人多数都会需要使用到 session (会话),我们使用 session 来保存一些需要在两个不同的请求之间共享数据。一般 Java 的 Web 容器像 Tomcat、Resin、Jetty 等等,它们会在...

红薯
今天
3
0
C++ std::thread

C++11提供了std::thread类来表示一个多线程对象。 1,首先介绍一下std::this_thread命名空间: (1)std::this_thread::get_id():返回当前线程id (2)std::this_thread::yield():用户接口...

yepanl
今天
3
0
Nignx缓存文件与动态文件自动均衡的配置

下面这段nginx的配置脚本的作用是,自动判断是否存在缓存文件,如果有优先输出缓存文件,不经过php,如果没有,则回到php去处理,同时生成缓存文件。 PHP框架是ThinkPHP,最后一个rewrite有关...

swingcoder
今天
2
0
20180920 usermod命令与用户密码管理

命令 usermod usermod 命令的选项和 useradd 差不多。 一个用户可以属于多个组,但是gid只有一个;除了gid,其他的组(groups)叫做扩展组。 usermod -u 1010 username # 更改用户idusermod ...

野雪球
今天
3
0
Java网络编程基础

1. 简单了解网络通信协议TCP/IP网络模型相关名词 应用层(HTTP,FTP,DNS等) 传输层(TCP,UDP) 网络层(IP,ICMP等) 链路层(驱动程序,接口等) 链路层:用于定义物理传输通道,通常是对...

江左煤郎
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部