链表的一些算法问题

package com.jiyx.tesr.testLinked;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Random;

/**
 * 链表工具类
 * auther: jiyx
 * date: 2018/9/11.
 */
public class LinkedUtils {

    /**
     * 定义链表节点
     */
    @AllArgsConstructor
    @NoArgsConstructor
    @Data
    private static class Node {
        private int value;
        private Node next;
    }

    /**
     * 创建单向链表
     * @param len
     * @return
     */
    private static Node createUniaxialLinked(int len) {
        if (len <= 0) {
            return null;
        } else {
            return new Node(len, createUniaxialLinked(--len));
        }
    }

    /**
     * 创建单向带环链表
     * @param len
     * @return
     */
    private static Node createUniaxialLinkedCircle(int len) {
        Node linkedCircle = reverse4(createUniaxialLinked(len));
        Random random = new Random();
        int value = random.nextInt(len);
        getTail(linkedCircle).setNext(getNode(linkedCircle, value));
        return linkedCircle;
    }

    /**
     * 根据node中的value返回Node对象
     *
     * @param head
     * @param value
     * @return
     */
    private static Node getNode(Node head, int value) {
        Node curr = head;
        while (curr != null) {
            if (curr.getValue() == value) {
                return curr;
            }
            curr = curr.getNext();
        }
        return null;
    }

    /**
     * 获取链表的尾节点
     * @param head
     * @return
     */
    private static Node getTail(Node head) {
        Node tail = null;
        Node curr = head;
        while (curr != null) {
            tail = curr;
            curr = curr.getNext();
        }
        return tail;
    }

    /**
     * 这里是单向链表，所以如果翻转的时候是从中间节点开始的话，会丢失前面的节点
     * 思路：获取当前节点，然后让当前节点指向他的头结点，然后他的下一个节点指向他
     * 这个是自己第一时间想到的，是最麻烦的
     *
     * @param node
     * @return
     */
    public static Node reverse(Node node) {
        Node curr = null;
        Node next = null;
        Node dNext = node;
        Node pNext = null;
        while (dNext != null) {
            // 设置当前节点
            curr = dNext;
            // 获取下一位的节点
            next = curr.getNext();
            // 将当前的链表和已经反转的链表相连
            curr.setNext(pNext);
            if (next != null) {
                // 获取链表的第三个节点，也就是需要进行下次翻转的开头
                dNext = next.getNext();
            } else {
                // 将当前的链表和已经反转的链表相连，这里处理的是只剩一位
                return curr;
            }
            // 翻转
            next.setNext(curr);
            // 记录已翻转的头结点
            pNext = next;
        }
        return pNext;
    }

    /**
     * 链表翻转2
     * 思路：创建一个新的链表，将原链表由头开始，一个个放入新链表即可，贼简单
     * @param node
     * @return
     */
    public static Node reverse2(Node node) {
        // 新链表表头
        Node newNodeHead = null;
        // 当前节点
        Node curr = node;
        // 下一个节点
        Node next = null;
        while (curr != null) {
            // 获取下一个节点
            next = curr.getNext();
            // 将当前节点放入新链表中
            curr.setNext(newNodeHead);
            // 重置new链表的表头
            newNodeHead = curr;
            // 下一位
            curr = next;
        }
        return newNodeHead;
    }

    /**
     * 链表翻转3
     * 思路：移位，如1->2->3->4->5
     * 第一次移位，变为2->1->3->4->5
     * 第二次移位，变为3->2->1->4->5
     * 以此类推，这个也是蛮简单的
     * @param node
     * @return
     */
    public static Node reverse3(Node node) {
        // 下一个节点
        Node next = node.getNext();
        // 头结点
        Node head = node;
        while (next != null) {
            // node一直指向开始的头结点，设置他的下一个节点
            node.setNext(next.getNext());
            // 将跳过的节点设置到表头
            next.setNext(head);
            // 重置表头
            head = next;
            // 下一位
            next = node.getNext();
        }
        return head;
    }

    /**
     * 链表翻转，跟上一个实现的细节不太一样而已
     * 思路：同上
     * 原链表：1-2-3-4-5
     * 第一步：2-1-3-4-5
     * 第二部：3-2-1-4-5
     * 知道最后
     * @param head
     */
    public static Node reverse4(Node head){

        if (head == null) {
            return null;
        }

        // 尾节点
        Node tail = head;
        Node next = null;

        while (tail.getNext() != null) {
            next = tail.getNext();
            // 删除next节点
            tail.setNext(next.getNext());
            // 将next放于表头
            next.setNext(head);
            // 重新设置头结点
            head = next;
        }
        return next;
    }

    /**
     * 根据步长翻转，这个方法的思路是根据步长截取每段，然后进行翻转，然后拼接.单向链表，这个写起来感觉很麻烦
     * @param node
     * @param step
     * @return
     */
    public static Node reverse(Node node, int step) {
        // 当前头结点，翻转之后的尾节点
        Node currHead = null;
        // 下一个头结点
        Node nextHead = node;
        // 当前结点，用于计算尾节点
        Node curr = null;
        // 上一个的尾节点
        Node pTail = null;
        // 这里设置为null是为了为node重新赋值
        node = null;
        while (nextHead != null) {
            // 存储上步的尾节点，为下面使用
            pTail = currHead;
            curr = currHead = nextHead;
            // 根据步长找到尾节点
            for (int i = 0; i < step - 1; i++) {
                if (curr.getNext() != null) {
                    curr = curr.getNext();
                }
            }
            // 记录下一个步长开始位置
            nextHead = curr.getNext();
            // 将当前节点独立出来进行翻转
            curr.setNext(null);
            // 链表翻转，这里没用接收结果是因为，翻转完之后头变尾，尾变头
            reverse(currHead);
            if (pTail != null) {
                // 由于单链表翻转丢失前端节点，所以这里在翻转完成之后再进行链表的连接
                pTail.setNext(curr);
            }
            // 这里从新设定表头
            if (node == null) {
                node = curr;
            }
        }
        return node;
    }

    /**
     * 链表按照指定的步长进行翻转
     * 思路：
     *
     * @param head
     * @param step
     * @return
     */
    public static Node reverse7(Node head, int step) {

        // 上一个的尾节点
        Node pTail = null;
        // 翻转后的表头
        Node linkedHead = null;
        // 表头是否已经设置
        boolean headAready = false;
        // 是否是第一次设置
        boolean isFirst = true;
        int count;
        while (head != null) {
            // 重置步长
            count = step;
            // 这一部分就是链表发展，思路就是移位。1-2-3-4，2-1-3-4，3-2-1-4
            Node tail = head;
            Node next = null;
            while (tail.getNext() != null && --count > 0) {
                next = tail.getNext();
                tail.setNext(next.getNext());
                next.setNext(head);
                head = next;
            }

            // 赌一次设置表头
            if (!headAready) {
                linkedHead = head;
                headAready = true;
                isFirst = false;
            }else {
                // 不是第一次要讲新的翻转后的链表和上一步的尾节点对接
                pTail.setNext(head);
            }

            pTail = tail;
            head = tail.getNext();
        }
        return linkedHead;
    }

    /**
     * 校验链表中是否有环
     * 思想：使用快慢指针进行校验，如果快慢指针重合的话,这个是根据网上资料获取的思路
     * @param head
     * @return
     */
    public static boolean checkLinkedHaveCircle(Node head) {
        Node slow = head;
        Node faster = head;

        while (slow != null && faster != null) {
            // 慢指针前进一步
            slow = slow.getNext();
            // 快指针前进两步
            faster = faster.getNext() != null ? faster.getNext().getNext() : null;
            if (slow == faster) {
                System.out.println("相同的节点value是：" + slow.getValue());
                return true;
            }
        }

        return false;
    }

    /**
     * 合并两个有序的链表
     * 思路：两个链表进行比较
     * @param curr
     * @param other
     * @return
     */
    public static Node mergeSortedLinked(Node curr, Node other) {
        // 新表头，这里有一个哨兵节点
        Node newNode = new Node();
        Node tail = newNode;
        while (curr != null && other != null) {
            // 将较小的先放入链表
            if (curr.getValue() <= other.getValue()) {
                tail.setNext(curr);
                curr = curr.getNext();
            } else {
                tail.setNext(other);
                other = other.getNext();
            }

            // 重置表尾
            tail = tail.getNext();
        }

        // 合并完成剩下的
        if (curr != null) {
            tail.setNext(curr);
        }

        if (other != null) {
            tail.setNext(other);
        }
        // 返回的时候将哨兵节点剔除
        return newNode.getNext();
    }

    /**
     * 删除链表末尾的n个节点
     * 思想：
     * 链表翻转，删除n个节点，然后再翻转
     * @param head
     * @param n
     */
    public static Node deleteLastNodes(Node head, int n) {

        // n小于1
        if (n < 1) {
            throw new IllegalArgumentException("删除的节点数不能小于等于0");
        }
        // head为空
        if (head == null) {
            throw new IllegalArgumentException("节点不能为空");
        }

        head = reverse4(head);
        while (n-- > 0) {
            head = head.getNext();
        }

        // 如果n超出了链表长度
        if (head == null && n > 0) {
            throw new IllegalArgumentException("n超出了链表长度");
        }

        return reverse4(head);
    }

    /**
     * 删除链表的第index个节点
     * 思路：遍历删除，感觉很蠢
     * @param head
     * @param index
     */
    public static Node deleteNodeByIndex(Node head, int index) {
        if (head == null) {
            throw new IllegalArgumentException("链表不能为空");
        }

        if (index == 1) {
            return head.getNext();
        }

        Node curr = head;

        // 前一个节点
        Node preNode = null;
        while (curr != null && --index > 0) {
            preNode = curr;
            curr = curr.getNext();
        }

        if (index > 0 && curr == null) {
            throw new IllegalArgumentException("index 超出范围");
        }

        preNode.setNext(curr.getNext());
        return head;
    }

    /**
     * 删除链表倒数的第n个节点
     * @param head
     * @param reverseIndex
     * @return
     */
    public static Node deleteNodeByReverseIndex(Node head, int reverseIndex) {
        head = reverse4(head);
        head = deleteNodeByIndex(head, reverseIndex);
        return reverse4(head);
    }

    /**
     * 求链表的中间节点
     * 思想：利用快慢指针查找中间节点
     * @param head
     */
    public static Node findMiddleNode(Node head) {

        if (checkLinkedHaveCircle(head)) {
            throw new IllegalArgumentException("入参链表是环状链表");
        }

        Node slow = head;
        Node high = head;
        while (high != null) {
            // 慢指针一位
            slow = slow.getNext();
            // 快指针两位
            high = high.getNext() != null ? high.getNext().getNext() : null;
            // 奇数位节点
            if (high != null && high.getNext() == null) {
                return slow;
            }
        }
        return slow;
    }

    public static void main(String[] args) {
        /*Node node = createUniaxialLinked(2);
        node = reverse5(node);
        node = reverse7(node, 2);
        System.out.println();*/
//        Node uniaxialLinked = createUniaxialLinked(10);
//        Node linkedCircle = createUniaxialLinkedCircle(6);
//        System.out.println(checkLinkedHaveCircle(linkedCircle));
//        System.out.println(checkLinkedHaveCircle(uniaxialLinked));
//        Node fir = createUniaxialLinked(6);
//        Node sec = createUniaxialLinked(5);
//        fir = reverse5(fir);
//        sec = reverse5(sec);
//        Node node = mergeSortedLinked(fir, sec);
//        sec = reverse4(sec);
//        System.out.println(findMiddleNode(sec));
        Node sec = createUniaxialLinked(5);
//        sec = deleteNodeByIndex(sec, 5);
//        sec = deleteLastNodes(sec, 2);
        sec = deleteNodeByReverseIndex(sec, 2);
        System.out.println();
    }

}