自己实现一个单链表 以及 单链表的 LRU算法回文判断算法

package linkedlist;


import java.util.Scanner;

/**
 * Describe:单链表
 * Author: 九霄道长
 * CreateTime: 2021/12/17 17:53
 */

public class SingleList<T> {

    private Node head;

    private Integer length;

    //LRU 算法的容量
    private Integer capacity = 10;

    public class Node<T> {
        private T e;
        private Node next;

        public Node(T e) {
            this.e = e;
        }

        public Node(T e, Node next) {
            this.e = e;
            this.next = next;
        }

        public T getE() {
            return e;
        }

        public void setE(T e) {
            this.e = e;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        public Node() {
        }
    }

    public SingleList() {
        this.head = new Node();
        this.length = -1;
    }

    /**
     * 添加一个元素到链表头部
     *
     * @param e
     */
    public void addHead(T e) {
        //向头部添加节点 先把原来的节点暂存起来
        Node node = this.head.getNext();
        //把节点添加到头部
        this.head.setNext(new Node(e, node));
        length++;
    }

    /**
     * 添加一个元素到链表尾部
     *
     * @param e
     */
    public void addTail(T e) {
        Node node = this.head;
        while (node.getNext() != null) {
            node = node.getNext();
        }
        node.setNext(new Node(e));
        length++;
    }

    /**
     * 制定位置添加一个元素
     *
     * @param index
     * @param e
     */
    public void add(int index, T e) {
        checkIndex(index);
        Node node = findIndexAgo(index);
        node.getNext().setNext(new Node(e, node.getNext().getNext()));
        length++;
    }

    /**
     * 更新指定位置的元素
     *
     * @param index
     * @param e
     */
    public void updateIndex(int index, T e) {
        checkIndex(index);
        Node indexAgo = findIndexAgo(index);
        indexAgo.getNext().setE(e);
    }

    /**
     * 删除指定位置的元素
     *
     * @param index
     */
    public void deleteIndex(int index) {
        checkIndex(index);
        Node indexAgo = findIndexAgo(index);
        indexAgo.setNext(indexAgo.getNext().getNext());
        length--;
    }

    /**
     * 根据前驱节点删除下一个节点
     *
     * @param node
     */
    public void deleteElemOptim(Node node) {
        node.setNext(node.getNext().getNext());
        length--;
    }

    //根据下标找到前驱节点
    public Node findIndexAgo(int index) {
        checkIndex(index);
        Node node = this.head;
        int i = 0;
        while (node.getNext() != null) {

            if (i == index) {
                return node;
            }
            node = node.getNext();
            i++;
        }
        return node;
    }

    //根据下标找到节点
    public Node findIndex(int index) {
        checkIndex(index);
        Node node = this.head;
        int i = 0;
        while (node.getNext() != null) {
            if (i == index) {
                return node.getNext();
            }
            node = node.getNext();
            i++;
        }
        return null;
    }

    //根据元素寻找前驱节点
    public Node findNode(T e) {
        Node node = this.head;
        while (node.getNext() != null) {
            if (node.getNext().getE().equals(e)) {
                return node;
            }
            node = node.getNext();
        }
        return null;
    }

    public void printAll() {
        Node node = this.head;
        while (node.getNext() != null) {
            System.out.print(node.getNext().getE() + ",");
            node = node.getNext();
        }
        System.out.println();
    }

    public void checkIndex(int index) {
        if (index < 0 || index > length) {
            throw new IllegalArgumentException("下标越界");
        }
    }

    public void LRU(T e) {
        if (length >= capacity) {
            Node node = findNode(e);
            if (node != null) {
                deleteElemOptim(node);
            } else {
                deleteIndex(length);
            }

        }
        addHead(e);
    }

    private Node getHead() {
        return head;
    }

    private void setHead(Node head) {
        this.head = head;
    }

    private Integer getLength() {
        return length;
    }

    private void setLength(Integer length) {
        this.length = length;
    }

    private boolean Palindrome(SingleList Node) {
        Node node = Node.head.getNext();
        Node quick = node;
        Node slow = node;
        Node reverse = null;
        while (quick != null && quick.getNext() != null) {
            //快指针 走两步
            quick = quick.getNext().getNext();

            //翻转前半部分链表
            //先暂存 慢指针  走一步
            Node next = slow.getNext();

            //把前面的元素放到后面
            slow.setNext(reverse);
            //反转的结果 给了 逆向
            reverse = slow;
            slow = next;
        }
        if (quick != null) {
            slow = slow.getNext();
        }
        while (slow != null) {
            if (!slow.getE().equals(reverse.getE())) {
                return false;
            }
            slow = slow.getNext();
            reverse = reverse.getNext();
        }
        return true;
    }

    public static void main(String[] args) {
        SingleList singleList = new SingleList();
//        singleList.addHead("1");
//        singleList.addHead("2");
//        singleList.addHead("3");
//        singleList.addHead("4");
//        singleList.printAll();
        //增
//        singleList.addTail("1");
//        singleList.addTail("2");
//        singleList.addTail("3");
//        singleList.add(1,"ce");
//        //删
//        singleList.deleteIndex(2);
//        //改
//        singleList.updateIndex(2,"修改");
//        //查
//        singleList.printAll();

        //单链表之LRU算法
//        Scanner scanner = new Scanner(System.in);
//        while (true){
//            int i = scanner.nextInt();
//            singleList.LRU(i);
//            singleList.printAll();
//        }
        //单链表判断回文串
        singleList.addTail("1");
        singleList.addTail("2");
        singleList.addTail("1");

        System.out.println(singleList.Palindrome(singleList));
    }
}