单链表，双链表反转

package class03;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 单链表，双链表反转
 */
public class Code01_ReverseList {
    public static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    public static class DoubleNode {
        int value;
        DoubleNode pre;
        DoubleNode next;

        public DoubleNode(int value) {
            this.value = value;
        }
    }

    /**
     * 反转单链表
     *
     * @param head 头节点
     * @return 反转后的头节点
     */
    public static Node reverseNodeList(Node head) {
        Node pre = null;
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 反转双链表
     *
     * @param head 头节点
     * @return 反转后的头节点
     */
    public static DoubleNode reverseDoubleNodeList(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            //head.pre = pre;//很隐蔽的问题。只打印每一个节点的next，发现不了这个问题。
            head.pre = next;
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 打印单链表
     *
     * @param head 头节点
     */
    public static void printNodeList(Node head) {
        while (head != null) {
            System.out.print(head.value + "->");
            head = head.next;
        }
        System.out.println("null");
    }

    /**
     * 打印双链表
     *
     * @param head 头节点
     */
    public static void printDoubleNodeList(DoubleNode head) {
        System.out.print("      ");
        DoubleNode end = null;
        while (head != null) {
            System.out.print(head.value + "->");
            end = head;
            head = head.next;
        }
        System.out.println("null");
        List<DoubleNode> list = new ArrayList<>();
        while (end != null) {
            list.add(end);
            end = end.pre;
        }
        System.out.print("null");
        for (int i = list.size() - 1; i >= 0; i--) {
            DoubleNode doubleNode = list.get(i);
            System.out.print("<~" + doubleNode.value);//"<~"：向前的指针，也就是pre。
        }
        System.out.println();
    }

    /**
     * 借助ArrayList实现单链表反转
     *
     * @param head 头节点
     * @return 反转后的头节点
     */
    public static Node testReverseNodeList(Node head) {
        ArrayList<Node> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        list.get(0).next = null;
        int N = list.size();
        for (int i = 1; i < N; i++) {
            list.get(i).next = list.get(i - 1);
        }
        return list.get(N - 1);
    }

    /**
     * 自己参照，借助ArrayList实现单链表反转(testReverseNodeList())，实现的。
     * 测试反转双链表
     *
     * @param head 头节点
     * @return 反转后的头节点
     */
    public static DoubleNode testReverseDoubleNodeList2(DoubleNode head) {
        if (head == null) {
            return null;
        }
        List<DoubleNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        list.add(head);
        list.get(0).next = null;
        list.get(0).pre = list.get(1);
        int N = list.size();
        for (int i = 1; i < N - 1; i++) {
            list.get(i).next = list.get(i - 1);
            list.get(i).pre = list.get(i + 1);
        }
        return list.get(N - 2);
    }

    public static DoubleNode testReverseDoubleNodeList(DoubleNode head) {
        if (head == null) {
            return null;
        }
        ArrayList<DoubleNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        int N = list.size();
        list.get(0).next = null;
        DoubleNode pre = list.get(0);
        for (int i = 1; i < N; i++) {
            DoubleNode cur = list.get(i);
            cur.next = pre;
            cur.pre = null;
            pre.pre = cur;
            pre = cur;
        }
        return list.get(N - 1);
    }

    /**
     * 生成随机的单链表
     *
     * @param size  要生成单链表的长度
     * @param value 要生成的单链表的每一个节点的最大值
     * @return 生成的随机单链表的头节点
     */
    public static Node generateRandomNodeList(int size, int value) {
        int num = (int) (Math.random() * (value + 1));
        Node head = new Node(num);
        Node pre = head;
        size--;
        while (size != 0) {
            Node cur = new Node((int) (Math.random() * (value + 1)));
            pre.next = cur;
            pre = cur;
            size--;
        }
        return head;
    }

    public static DoubleNode generateRandomDoubleNodeList(int size, int value) {
//        (int)();
        DoubleNode head = new DoubleNode((int) (Math.random() * (value + 1)));
        DoubleNode pre = head;
        while (size != 0) {
            DoubleNode cur = new DoubleNode((int) (Math.random() * (value + 1)));
            pre.next = cur;
            cur.pre = pre;
            pre = cur;
            size--;
        }
        return head;
    }

    /**
     * for test
     * 获取单链表原始的顺序
     *
     * @param head 头节点
     * @return 单链表原始的顺序list
     */
    public static List<Integer> getNodeListOriginalOrder(Node head) {
        List<Integer> originalOrderList = new ArrayList<>();
        while (head != null) {
            originalOrderList.add(head.value);
            head = head.next;
        }
        return originalOrderList;
    }

    /**
     * for test
     * 获取双链表原始的顺序
     *
     * @param head 头节点
     * @return 双链表原始的顺序list
     */
    public static List<Integer> getDoubleNodeOriginalOrder(DoubleNode head) {
        List<Integer> doubleNodeOriginalOrderList = new ArrayList<>();
        while (head != null) {
            doubleNodeOriginalOrderList.add(head.value);
            head = head.next;
        }
        return doubleNodeOriginalOrderList;
    }

    /**
     * 检查单链表反转，是否正确。
     *
     * @param originalOrderList 单链表的原始顺序
     * @param head              单链表头节点
     * @return 单链表反转，是否正确
     */
    public static boolean checkNodeListReverse(List<Integer> originalOrderList, Node head) {
        for (int i = originalOrderList.size() - 1; i >= 0; i--) {
            if (!originalOrderList.get(i).equals(head.value)) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    /**
     * 检查双链表反转，是否正确。
     *
     * @param doubleNodeOriginalOrderList 双链表的原始顺序
     * @param head                        双链表头节点
     * @return 双链表反转，是否正确
     */
    public static boolean checkDoubleNodeListReverse(List<Integer> doubleNodeOriginalOrderList, DoubleNode head) {
        DoubleNode end = null;
        for (int i = doubleNodeOriginalOrderList.size() - 1; i >= 0; i--) {
            if (!doubleNodeOriginalOrderList.get(i).equals(head.value)) {
                return false;
            }
            end = head;//end就一直跟着head，只要head在本次循环一跳步，那么在下一次循环中，end就来到head的位置。
            head = head.next;//head节点向后跳步
        }
        //此时end来到了，链表的末尾。
        for (int i = 0; i < doubleNodeOriginalOrderList.size(); i++) {
            if (!doubleNodeOriginalOrderList.get(i).equals(end.value)) {
                return false;
            }
            end = end.pre;//end节点向前跳步
        }
        return true;
    }

    public static void main(String[] args) {
        int size = 10;
        int value = 100;
        int testTimes = 100000;
        System.out.println("单链表，双链表反转，测试开始！");
        for (int i = 0; i < testTimes; i++) {
            Node node1 = generateRandomNodeList(size, value);
            List<Integer> list1 = getNodeListOriginalOrder(node1);
            Node node2 = reverseNodeList(node1);
            if (!checkNodeListReverse(list1, node2)) {
                System.out.println("oops1!");
            }
            //用于查看结果。反转后的数组(list1)和反转后的链表比对。打开注释即可。
//            if (checkNodeListReverse(list1, node2) && i <= 2) {
//                Collections.reverse(list1);
//                System.out.println("list1 = " + list1);
//                printNodeList(node2);
//            }
            Node node3 = generateRandomNodeList(size, value);
            List<Integer> list2 = getNodeListOriginalOrder(node3);
            Node node4 = testReverseNodeList(node3);
            if (!checkNodeListReverse(list2, node4)) {
                System.out.println("oops2!");
            }
            //用于查看结果。反转后的数组(list2)和反转后的链表比对。打开注释即可。
//            if (checkNodeListReverse(list2, node4) && i <= 2) {
//                Collections.reverse(list2);
//                System.out.println("list2 = " + list2);
//                printNodeList(node4);
//            }

            DoubleNode doubleNode1 = generateRandomDoubleNodeList(size, value);
            List<Integer> list3 = getDoubleNodeOriginalOrder(doubleNode1);
            DoubleNode doubleNode2 = reverseDoubleNodeList(doubleNode1);
            if (!checkDoubleNodeListReverse(list3, doubleNode2)) {
                System.out.println("oops3!");
            }
            //用于查看结果。反转后的数组(list3)和反转后的链表比对。打开注释即可。
//            if (checkDoubleNodeListReverse(list3, doubleNode2) && i <= 2) {
//                Collections.reverse(list3);
//                System.out.println("list3 = " + list3);
//                printDoubleNodeList(doubleNode2);
//            }

            DoubleNode doubleNode3 = generateRandomDoubleNodeList(size, value);
            List<Integer> list4 = getDoubleNodeOriginalOrder(doubleNode3);
            DoubleNode doubleNode4 = testReverseDoubleNodeList(doubleNode3);
            if (!checkDoubleNodeListReverse(list4, doubleNode4)) {
                System.out.println("oops4!");
            }
            //用于查看结果。反转后的数组(list4)和反转后的链表比对。打开注释即可。
//            if (checkDoubleNodeListReverse(list4, doubleNode4) && i <= 2) {
//                Collections.reverse(list4);
//                System.out.println("list4 = " + list4);
//                printDoubleNodeList(doubleNode4);
//            }
        }
        System.out.println("单链表，双链表反转，测试结束！！！！！");
    }
}