1.统计出单链表HL中结点的值等于给定值X的结点数。import java.util.*; import java.io.*; //定义单链表节点类 class ListNode{ int val; ListNode next; ListNode(int val){ this.val val; this.next null; } } public class Main1{ public static int countNodes(ListNode head, int x){ int count 0; ListNode current head; while(current ! null){ if (current.val x){ count; } current current.next; } return count; } public static void main(String[] args){ //输入单链表的val值 Scanner sc new Scanner(System.in); String[] nums sc.nextLine().split( ); //创建链表 ListNode head new ListNode(-1); ListNode curr head; for(String s : nums){ int val Integer.parseInt(s); curr.next new ListNode(val); curr curr.next; } //读取x值 int x sc.nextInt(); //调用方法获取结果 int count countNodes(head,x); } }2.快速排序import java.util.*; //挖坑法的快排 public class Main2 { //对外暴露的函数 public static void quickSort(int[] arr){ if(arr null || arr.length 1){ return; } hoareQuickSort(arr, 0, arr.length - 1); } private static void hoareQuickSort(int[] arr, int low, int high){ if(low high){ int pivotPos partition(arr, low, high); hoareQuickSort(arr, low, pivotPos - 1); hoareQuickSort(arr, pivotPos 1, high); } } //划分分区并返回已排序好元素的下标 private static int partition(int[] arr, int low, int high){ int pivot arr[low]; int left low; int right high; while(left right){ //必须严格确保leftright //右边找大 while(left right arr[right] pivot){ right--; } //左边找小 while(left right arr[left] pivot){ left; } if(left right){ swap(arr, left, right); } } swap(arr, low, right); return right; } //辅助函数交换两个位置的元素 private static void swap(int[] arr, int i, int j){ int temp arr[i]; arr[i] arr[j]; arr[j] temp; } }3、设有两个集合A和集合B要求设计生成集合CA∩B的算法其中集合A、B和C用链式存储结构表示。import java.util.*; class ListNode{ int val; ListNode next; ListNode(int val){ this.val val; this.next null; } } public class Main3 { public static void main(String[] args){ Scanner sc new Scanner(System.in); //创建集合A int lengthA sc.nextInt(); int[] arrA new int[lengthA]; for(int i 0; i lengthA;i){ arrA[i] sc.nextInt(); } ListNode A buildList(arrA); //创建集合B int lengthB sc.nextInt(); int[] arrB new int[lengthB]; for (int i 0; i lengthB; i) { arrB[i] sc.nextInt(); } ListNode B buildList(arrB); //计算集合C ListNode C intersection(A, B); printList(C); } //创建链表 public static ListNode buildList(int[] nums){ if(nums null || nums.length 0){ return null; } //头结点 ListNode dummy new ListNode(-1); ListNode curr dummy; for(int num : nums){ curr.next new ListNode(num); curr curr.next; } return dummy.next; } //计算交集 public static ListNode intersection(ListNode A, ListNode B){ //创建集合A SetInteger setA new HashSet(); ListNode p A; while(p ! null){ setA.add(p.val); p p.next; } //计算A∩B SetInteger setC new HashSet(); ListNode q B; while(q ! null){ if (setA.contains(q.val)){ //加入set自动去重 setC.add(q.val); } q q.next; } //将集合C转化为链式存储结构 ListNode dummy new ListNode(-1); ListNode curr dummy; for(int num : setC){ curr.next new ListNode(num); curr curr.next; } return dummy.next; } //打印输出 public static void printList(ListNode head){ if (head null){ System.out.println( ); } ListNode curr head; while(curr ! null){ System.out.print(curr.val ); curr curr.next; } } }复盘错误的计算交集的函数原因是因为没有考虑到去重public static ListNode intersection(ListNode A, ListNode B){ //创建集合A SetInteger setA new HashSet(); ListNode p A; while(p ! null){ setA.add(p.val); p p.next; } //查找交集 ListNode dummy new ListNode(-1); ListNode curr dummy; ListNode q B; while(q ! null){ if(setA.contains(q.val)){ curr.next new ListNode(q.val); curr curr.next; } q q.next; } return dummy.next; }4、设计一个求结点x在二叉树中的双亲结点算法。package Main4; import java.util.*; class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(int val){ this.val val; this.left null; this.right null; } } public class Main4 { private static TreeNode parent null; public static void main(String[] args){ Scanner sc new Scanner(System.in); // 输入格式 // 第一行二叉树层序序列空结点用-1表示如 1 2 3 -1 4 -1 5 表示根1左2右32的右43的右5 // 第二行要查找的结点值x String[] nodeStrs sc.nextLine().split( ); int[] nodes new int[nodeStrs.length]; for(int i 0; i nodeStrs.length; i){ nodes[i] Integer.parseInt(nodeStrs[i]); } int x sc.nextInt(); //构建二叉树 TreeNode root buildTree(nodes); parent null; TreeNode parentNode findParent(root,x); } //构建二叉树,最终并返回根节点 public static TreeNode buildTree(int[] nodes){ if (nodes null || nodes.length 0 || nodes[0] -1){ return null; } TreeNode root new TreeNode(nodes[0]); //用数组模拟队列 TreeNode[] queue new TreeNode[nodes.length]; int front 0; int rear 0; queue[rear] root; int index 1; while(front rear index nodes.length){ TreeNode curr queue[front]; //添加左孩子 if(nodes[index] ! -1){ curr.left new TreeNode(nodes[index]); queue[rear] curr.left; } index; //添加右孩子 if (nodes[index] ! -1 index nodes.length){ curr.right new TreeNode(index); queue[rear] curr.right; } index; } return root; } //查找节点x的父节点 public static TreeNode findParent(TreeNode root, int x){ if (root null || parent ! null){ return null; } if ((root.left ! null root.left.val x) || (root.right ! null root.right.val x)){ parent root; return parent; } findParent(root.left, x); if (parent null){ findParent(root.right, x); } return parent; } }复盘层次遍历二叉树需要借助队列来构建。因为在使用层次遍历创建二叉树时本质上是按层处理节点而队列的先进先出的特性能够保证按序处理。e.g.处理数组[1,2,3,null,null,4,5]第一步创建根节点1此时它需要分配左、右孩子把它加入队列。第二步取出队列头部的1为它分配左孩子2、右孩子3然后把2和3加入队列然后依次为他们分配孩子。在判断parent的左右孩子值是否为x时必须先保证parent的左右孩子不为空所以判断条件必须写成if ((root.left ! null root.left.val x) || (root.right ! null root.right.val x))而不是if (root.left.val x || root.right.val x)5、设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符),要求利用原单链表中结点空间设计出三个单链表的算法使每个单链表只包含同类字符。package Main5; import java.util.*; //链表节点类 class ListNode{ char val; ListNode next; ListNode(char val){ this.val val; this.next null; } } public class Main5 { public static void main(String[] args){ Scanner sc new Scanner(System.in); // 输入格式输入一个字符串且仅包含上述三类字符如 A1b2C!3d String input sc.nextLine(); //构建单链表 ListNode head buildList(input); //拆分链表 ListNode[] result splitList(head); ListNode letterList result[0]; ListNode numberList result[1]; ListNode otherList result[2]; //输出结果 printList(letterList); } public static ListNode buildList(String s){ if(s null || s.isEmpty()){ return null; } ListNode dummy new ListNode( ); ListNode curr dummy; for(char c : s.toCharArray()){ curr.next new ListNode(c); curr curr.next; } return null; } public static ListNode[] splitList(ListNode head){ //为三个单链表创建虚拟头结点 ListNode letterDummy new ListNode( ); ListNode numberDummy new ListNode( ); ListNode otherDummy new ListNode( ); //使用尾插法为三个单链表添加元素 ListNode letterTail letterDummy; ListNode numberTail numberDummy; ListNode otherTail otherDummy; ListNode curr head; while(curr ! null){ ListNode nextNode curr.next; if (Character.isUpperCase(curr.val)){ letterTail.next curr; letterTail curr; } else if (Character.isDefined(curr.val)) { numberTail.next curr; numberTail curr; }else { otherTail.next curr; otherTail curr; } curr.next null; curr nextNode; } return new ListNode[]{letterDummy.next, numberDummy.next, otherDummy.next}; } public static void printList(ListNode head){ if (head null){ System.out.println(空); return; } ListNode curr head; while(curr ! null){ System.out.print(curr.val ); curr curr.next; } } }复盘链表中头结点的使用如果不用头结点 在链表中后续追加节点的时候必须在循环中加if (head null)的判断区分 “第一次创建头节点” 和 “后续追加节点”。而使用虚拟头结点后dummy作为 “固定的前驱节点”无论链表是否为空所有有效节点都可以通过curr.next插入循环中无需判断 “是否是第一个节点”。且避免空指针异常如果没有dummy当链表为空时比如字符串长度为 0curr会是null调用curr.next会直接抛空指针而dummy是始终存在的节点curr初始指向dummy即使链表为空curr.next也只是null不会报错。6、设计在链式存储结构上交换二叉树中所有结点左右子树的算法。package Main6; import java.util.*; //定义二叉树节点 class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(int val){ this.val val; this.left null; this.right null; } } public class Main6 { public static void main(String[] args){ Scanner sc new Scanner(System.in); //输入二叉树层序序列,空结点用-1表示,空格分割 String[] nodeStrs sc.nextLine().split( ); int[] nodes new int[nodeStrs.length]; for (int i 0; i nodeStrs.length; i) { nodes[i] Integer.parseInt(nodeStrs[i]); } //构建二叉树 TreeNode root buildTree(nodes); System.out.println(交换前前序遍历); preOrder(root); System.out.println(); //交换二叉树所有节点的左右子树 invertTree(root); System.out.println(交换后前序遍历); preOrder(root); } //层次遍历构建二叉树 public static TreeNode buildTree(int[] nodes){ if (nodes null || nodes.length 0 || nodes[0] -1){ return null; } TreeNode root new TreeNode(nodes[0]); TreeNode[] queue new TreeNode[nodes.length]; int front 0; int rear 0; queue[rear] root; int index 1; while(front rear index nodes.length){ TreeNode curr queue[front]; //构建左子节点 if (nodes[index] ! -1){ curr.left new TreeNode(nodes[index]); queue[rear] curr.left; } index; //构建右子节点 if (nodes[index] ! -1 index nodes.length){ curr.right new TreeNode(nodes[index]); queue[rear] curr.right; } index; } return root; } //前序遍历打印二叉树 public static void preOrder(TreeNode root){ if (root null){ return; } System.out.print(root.val ); preOrder(root.left); preOrder(root.right); } //交换二叉树所有节点的左右子树 public static void invertTree(TreeNode root){ if (root null){ return; } invertTree(root.left); invertTree(root.right); TreeNode temp root.left; root.left root.right; root.right temp; } }复盘之所以采用后序遍历而不采用前序遍历是因为相较于前序遍历后序遍历更加直观。前序遍历的遍历顺序为根左右前序遍历的交换代码如下public static void invertTreePre(TreeNode root) { if (root null) return; TreeNode temp root.left; root.left root.right; root.right temp; invertTreePre(root.left); invertTreePre(root.right); }由于是先处理根节点所以在递归处理后续子节点时已是交换后的结果容易引起逻辑上的混乱。而后序遍历是从子节点开始处理处理父节点时子树结构已固定。7、在链式存储结构上建立一棵二叉排序树。package Main7; import java.util.*; //二叉树节点定义 class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val val; this.left null; this.right null; } } public class Main7 { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] nums new int[n]; for (int i 0; i n; i) { nums[i] sc.nextInt(); } //构建二叉排序树 TreeNode root buildBST(nums); inOrder(root); } //构建二叉搜索树 public static TreeNode buildBST(int[] nums){ TreeNode root null; for (int num : nums){ root insert(root,num); } return root; } public static TreeNode insert(TreeNode root, int num){ if (root null){ return new TreeNode(num); } if (num root.val){ root.left insert(root.left,num); } else if (num root.val){ root.right insert(root.right, num); } return root; } //中序遍历输出二叉排序树 public static void inOrder(TreeNode root){ if (root null){ return; } inOrder(root.left); System.out.print(root.val ); inOrder(root.right); } }复盘二叉排序树/二叉搜索树的特点左 根 右中序遍历出来为一个升序序列8、设计判断两个二叉树是否相同的算法。package Main8; import java.util.*; // 二叉树结点定义 class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val val; this.left null; this.right null; } } public class Main8 { public static void main(String[] args) { Scanner sc new Scanner(System.in); //构建第一个二叉树 System.out.println(请输入第一个二叉树的层序序列空结点用-1表示空格分隔); String[] str1 sc.nextLine().split( ); int[] nodes1 new int[str1.length]; for (int i 0; i str1.length; i) { nodes1[i] Integer.parseInt(str1[i]); } TreeNode root1 buildTree(nodes1); //构建第二个二叉树 System.out.println(请输入第一个二叉树的层序序列空结点用-1表示空格分隔); String[] str2 sc.nextLine().split( ); int[] nodes2 new int[str2.length]; for (int i 0; i str2.length; i) { nodes2[i] Integer.parseInt(str2[i]); } TreeNode root2 buildTree(nodes2); boolean result isSameTree(root1, root2); System.out.println(两棵二叉树是否相同: (result ? 是 : 否)); } //构建二叉树 public static TreeNode buildTree(int[] nodes){ if (nodes null || nodes.length 0 || nodes[0] -1){ return null; } TreeNode root new TreeNode(nodes[0]); TreeNode[] queue new TreeNode[nodes.length]; int front 0; int rear 0; queue[rear] root; int index 1; while (front rear index nodes.length){ TreeNode curr queue[front]; //构建左孩子 if (nodes[index] ! -1){ curr.left new TreeNode(nodes[index]); queue[rear] curr.left; } index; //构建右孩子 if (nodes[index] ! -1 index nodes.length){ curr.right new TreeNode(nodes[index]); queue[rear] curr.right; } index; } return root; } //判断两树是否相同 public static boolean isSameTree(TreeNode p, TreeNode q){ if (p null q null){ return true; } if ((p null q ! null) || (p ! null q null) ){ return false; } if (p.val ! q.val){ return false; } return isSameTree(p.left, q.left) isSameTree(p.right, q.right); } }复盘遍历二叉树的算法深度优先遍历先序、中序、后序广度优先遍历层次遍历9、设计两个有序单链表的合并排序算法。package Main9; import java.util.*; //链表节点 class ListNode { int val; ListNode next; ListNode(int val) { this.val val; this.next null; } } public class Main9 { public static void main(String[] args) { Scanner sc new Scanner(System.in); //构建第一个有序单链表 System.out.println(请输入第一个有序链表的长度); int n1 sc.nextInt(); int[] nums1 new int[n1]; System.out.println(请输入 n1 个升序整数空格分隔); for (int i 0; i n1; i) { nums1[i] sc.nextInt(); } ListNode l1 buildSortedList(nums1); //构建第二个有序单链表 System.out.println(请输入第二个有序链表的长度); int n2 sc.nextInt(); int[] nums2 new int[n2]; System.out.println(请输入 n2 个升序整数空格分隔); for (int i 0; i n2; i) { nums2[i] sc.nextInt(); } ListNode l2 buildSortedList(nums2); //合并 ListNode mergedList mergeTowList(l1, l2); System.out.println(合并后的有序链表); printList(mergedList); } //构建单链表 public static ListNode buildSortedList(int[] nums){ if (nums null || nums.length 0){ return null; } ListNode dummy new ListNode(-1); ListNode curr dummy; for (int num : nums){ curr.next new ListNode(num); curr curr.next; } return dummy.next; } public static ListNode mergeTowList(ListNode l1, ListNode l2){ ListNode dummy new ListNode(-1); //使用尾插法构建新链表 ListNode curr dummy; ListNode p l1; ListNode q l2; while (p ! null q ! null){ if (p.val q.val){ curr.next p; p p.next; }else { curr.next q; q q.next; } curr curr.next; } /*直接指向后序链表因为后序链表并没有断开*/ if (p ! null){ curr.next p; } if (q ! null){ curr.next q; } return dummy.next; } public static void printList(ListNode head){ if (head null){ System.out.println(链表为空); return; } ListNode curr head; while (curr ! null){ System.out.print(curr.val ); curr curr.next; } } }10、在顺序有序表中实现二分查找的算法。