java实现数组转链表、链表按指定起始位置反转,链表反转
java实现数组转链表、链表按指定起始位置反转,链表反转
leopardlz 发表于4个月前
java实现数组转链表、链表按指定起始位置反转,链表反转
  • 发表于 4个月前
  • 阅读 4
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

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;
    }
}

 

共有 人打赏支持
粉丝 0
博文 33
码字总数 4393
×
leopardlz
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: