1. 哈希表
2. 有序表
代码示例
import java.util.TreeMap;public class Test{public static void main(String[] args) {TreeMap<Integer, String> treeMap = new TreeMap<>();treeMap.put(1, "我是1");treeMap.put(4, "我是4");treeMap.put(9, "我是9");treeMap.put(3, "我是3");treeMap.put(5, "我是5");System.out.println("有序表中是否包含5：" + treeMap.containsKey(5));System.out.println("有序表中最小数是：" + treeMap.firstKey());System.out.println("有序表中最大数是：" + treeMap.lastKey());System.out.println("在有序表中，所有 <= 8 的数中，离 8 最近的数是：" + treeMap.floorKey(8));System.out.println("在有序表中，所有 >= 8 的数中，离 8 最近的数是：" + treeMap.ceilingKey(8));System.out.println("在有序表中，所有 <= 7 的数中，离 7 最近的数是：" + treeMap.floorKey(8));System.out.println("在有序表中，所有 <= 7 的数中，离 7 最近的数是：" + treeMap.ceilingKey(8));System.out.println("有序表中key为9的字符串是：" + treeMap.get(9));}}
3. 链表
代码示例
import java.util.TreeMap;public class Test{// 单向链表public static class Node{public int value;public Node next;// 构造函数public Node(int data){this.value = data;}}// 双向链表public static class DoubleNode{public int value;public DoubleNode last;public DoubleNode next;public DoubleNode(int data){this.value = data;}}// 反转单链表public static Node reverseList(Node head){Node pre = null;Node nex = null;while(head != null){nex = head.next;head.next = pre;pre = head;head = nex;}return pre;}// 反转双链表// 函数重载public static DoubleNode reverseList(DoubleNode head){DoubleNode pre = null;DoubleNode nex = null;while(head != null){nex = head.next;head.next = pre;head.last = nex;pre = head;head = nex;}return pre;}// 输出单链表public static void printLinkedList(Node head){System.out.print("单链表的输出结果是：");while (head != null) {System.out.print(head.value + " ");head = head.next;}System.out.println();}// 输出双链表public static void printDoubleLinkedList(DoubleNode head){System.out.print("双链表的输出结果是：");DoubleNode end = null;while (head != null){System.out.print(head.value + " ");end = head;head = head.next;}System.out.println();System.out.print("双链表的输出结果是：");while (end != null){System.out.print(end.value + " ");end = end.last;}System.out.println();}// 主函数public static void main(String[] args) {// 插入链表数据Node head1 = new Node(1);head1.next = new Node(2);head1.next.next = new Node(3);printLinkedList(head1);head1 = reverseList(head1);printLinkedList(head1);System.out.println();DoubleNode head2 = new DoubleNode(2);head2.next = new DoubleNode(3);head2.next.last = head2;head2.next.next = new DoubleNode(4);head2.next.next.last = head2.next;head2.next.next.next = new DoubleNode(5);head2.next.next.next.last = head2.next.next;printDoubleLinkedList(head2);printDoubleLinkedList(reverseList(head2));}
}
代码示例
import java.util.TreeMap;public class Test{// 单向链表public static class Node{public int value;public Node next;// 构造函数public Node(int data){this.value = data;}}public static void samePart(Node node1, Node node2){System.out.print("两个单链表相同的值为：");while (node1 != null && node2 != null){if(node1.value < node2.value) node1 = node1.next;else if(node1.value > node2.value) node2 = node2.next;else {System.out.print(node1.value + " ");node1 = node1.next;node2 = node2.next;}}}public static void printLinkedList(Node head){System.out.print("单链表输出的结果是：");while (head != null){System.out.print(head.value + " ");head = head.next;}System.out.println();}// 主函数public static void main(String[] args) {// 插入链表数据Node node1 = new Node(2);node1.next = new Node(3);node1.next.next = new Node(5);node1.next.next.next = new Node(6);Node node2 = new Node(1);node2.next = new Node(2);node2.next.next = new Node(5);node2.next.next.next = new Node(7);node2.next.next.next.next = new Node(8);printLinkedList(node1);printLinkedList(node2);// 打印公共部分samePart(node1, node2);}
}
O（1）空间复杂度的实现方法图解如图所示：
代码示例
import java.util.Stack;
import java.util.TreeMap;public class Test{// 单向链表public static class Node{public int value;public Node next;// 构造函数public Node(int data){this.value = data;}}// o(N)的空间复杂度函数public static boolean isPalindrome1(Node head){Stack<Node> stack = new Stack<>();// 使用临时变量Node cur = head;while(cur != null){stack.push(cur);cur = cur.next;}while (head != null){if(head.value != stack.pop().value) {return false;}head = head.next;}return true;}// o(N/2)的空间复杂度函数public static boolean isPalindrome2(Node head) {if(head == null || head.next == null)return true;// 快慢指针找到中点位置Node right = head.next; // 用来记录中点位置Node cur = head;while (cur.next != null && cur.next.next != null){right = right.next;cur = cur.next.next;}Stack<Node> stack = new Stack<>();while (right != null){stack.push(right);right = right.next;}while (!stack.isEmpty()){if(head.value != stack.pop().value)return false;head = head.next;}return true;}// O(1)的空间复杂度函数public static boolean isPalindrome3(Node head) {if(head == null || head.next == null)return true;Node n1 = head;Node n2 = head;while(n2.next != null && n2.next.next != null){n1 = n1.next;n2 = n2.next.next;}n2 = n1.next;n1.next = null;Node n3 = null;// 列表的倒序while (n2 != null) {n3 = n2.next; // 记录下一个节点的位置n2.next = n1;n1 = n2;n2 = n3;}n3 = n1; // last noden2 = head; // first nodeboolean res = true;while (n1 != null && n2 != null){if(n1.value != n2.value){res = false;break;}n1 = n1.next;n2 = n2.next;}// 还原链表n1 = n3.next;n3.next = null;while (n1 != null){n2 = n1.next;n1.next = n3;n3 = n1;n1 = n2;}return res;}// 输出链表public static void printLinkedList(Node head){System.out.print("单链表输出的结果是：");while (head != null){System.out.print(head.value + " ");head = head.next;}System.out.println();}// 主函数public static void main(String[] args) {// 插入链表数据Node head = null;printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);head.next.next = new Node(3);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);head.next.next = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);head.next.next = new Node(3);head.next.next.next = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);head.next.next = new Node(2);head.next.next.next = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);head.next.next = new Node(3);head.next.next.next = new Node(2);head.next.next.next.next = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");}
}
代码示例