数据结构-基于Java的算法和数据结构源码.zip

package class04; import java.util.ArrayList; import java.util.List; public class Code01_ReverseList { public static class Node { public int value; public Node next; public Node(int data) { value = data; } } public static class DoubleNode { public int value; public DoubleNode last; public DoubleNode next; public DoubleNode(int data) { value = data; } } public static Node reverseLinkedList(Node head) { Node pre = null; Node next = null; while (head != null) { next = head.next; head.next = pre; pre = head; head = next; } return pre; } public static DoubleNode reverseDoubleList(DoubleNode head) { DoubleNode pre = null; DoubleNode next = null; while (head != null) { next = head.next; head.next = pre; head.last = next; pre = head; head = next; } return pre; } public static Node testReverseLinkedList(Node head) { if (head == null) { return null; } 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); } public static DoubleNode testReverseDoubleList(DoubleNode head) { if (head == null) { return null; } ArrayList<DoubleNode> list = new ArrayList<>(); while (head != null) { list.add(head); head = head.next; } list.get(0).next = null; DoubleNode pre = list.get(0); int N = list.size(); for (int i = 1; i < N; i++) { DoubleNode cur = list.get(i); cur.last = null; cur.next = pre; pre.last = cur; pre = cur; } return list.get(N - 1); } // for test public static Node generateRandomLinkedList(int len, int value) { int size = (int) (Math.random() * (len + 1)); if (size == 0) { return null; } size--; Node head = new Node((int) (Math.random() * (value + 1))); Node pre = head; while (size != 0) { Node cur = new Node((int) (Math.random() * (value + 1))); pre.next = cur; pre = cur; size--; } return head; } // for test public static DoubleNode generateRandomDoubleList(int len, int value) { int size = (int) (Math.random() * (len + 1)); if (size == 0) { return null; } size--; 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.last = pre; pre = cur; size--; } return head; } // for test public static List<Integer> getLinkedListOriginOrder(Node head) { List<Integer> ans = new ArrayList<>(); while (head != null) { ans.add(head.value); head = head.next; } return ans; } // for test public static boolean checkLinkedListReverse(List<Integer> origin, Node head) { for (int i = origin.size() - 1; i >= 0; i--) { if (!origin.get(i).equals(head.value)) { return false; } head = head.next; } return true; } // for test public static List<Integer> getDoubleListOriginOrder(DoubleNode head) { List<Integer> ans = new ArrayList<>(); while (head != null) { ans.add(head.value); head = head.next; } return ans; } // for test public static boolean checkDoubleListReverse(List<Integer> origin, DoubleNode head) { DoubleNode end = null; for (int i = origin.size() - 1; i >= 0; i--) { if (!origin.get(i).equals(head.value)) { return false; } end = head; head = head.next; } for (int i = 0; i < origin.size(); i++) { if (!origin.get(i).equals(end.value)) { return false; } end = end.last; } return true; } public static void f(Node head) { head = head.next; } // for test public static void main(String[] args) { int len = 50; int value = 100; int testTime = 100000; System.out.println("test begin!"); for (int i = 0; i < testTime; i++) { Node node1 = generateRandomLinkedList(len, value); List<Integer> list1 = getLinkedListOriginOrder(node1); node1 = reverseLinkedList(node1); if (!checkLinkedListReverse(list1, node1)) { System.out.println("Oops1!"); } Node node2 = generateRandomLinkedList(len, value); List<Integer> list2 = getLinkedListOriginOrder(node2); node2 = testReverseLinkedList(node2); if (!checkLinkedListReverse(list2, node2)) { System.out.println("Oops2!"); } DoubleNode node3 = generateRandomDoubleList(len, value); List<Integer> list3 = getDoubleListOriginOrder(node3); node3 = reverseDoubleList(node3); if (!checkDoubleListReverse(list3, node3)) { System.out.println("Oops3!"); } DoubleNode node4 = generateRandomDoubleList(len, value); List<Integer> list4 = getDoubleListOriginOrder(node4); node4 = reverseDoubleList(node4); if (!checkDoubleListReverse(list4, node4)) { System.out.println("Oops4!"); } } System.out.println("test finish!"); } }