目录
常见问题总结
读取输入数据两种方法 （BufferedReader比较快，不容易出现报错）
1、Scanner s = new Scanner(System.in); int i = s.nextInt(); 2、BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] inputDate = br.readLine().trim().split(" ");int i = Integer.parseInt(inputDate[0]);
有一题while(fast.next.next != null && fast.next != null)出现了空指针异常的错误。正确应改为while(fast.next != null && fast.next.next != null)
第一章 栈和队列
CD5设计getMin功能的栈
描述
实现一个特殊功能的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
输入描述：
第一行输入一个整数N，表示对栈进行的操作总数。
下面N行每行输入一个字符串S，表示操作的种类。
如果S为"push"，则后面还有一个整数X表示向栈里压入整数X。
如果S为"pop"，则表示弹出栈顶操作。
如果S为"getMin"，则表示询问当前栈中的最小元素是多少。
输出描述：
对于每个getMin操作，输出一行表示当前栈中的最小元素是多少。
示例1
输入：
6push 3push 2push 1getMinpopgetMin输出：
12备注：
1<=N<=1000000-1000000<=X<=1000000数据保证没有不合法的操作
解答
import java.util.Scanner;import java.util.Stack;public class Main{public static class MyStack1{private Stack<Integer> stackData;private Stack<Integer> stackMin;public MyStack1(){this.stackData = new Stack<Integer>();this.stackMin = new Stack<Integer>();}public void push(int newNum){if (this.stackMin.isEmpty()){this.stackMin.push(newNum);}else if (newNum <= this.getMin()){this.stackMin.push(newNum);}this.stackData.push(newNum);}public int getMin(){if (this.stackMin.isEmpty()){throw new RuntimeException("Your stack is empty.");}return this.stackMin.peek();}public int pop(){if (this.stackData.isEmpty()){throw new RuntimeException("Your stack is empty.");}int value = this.stackData.pop();if (value == this.getMin()){this.stackMin.pop();}return value;}}public static class MyStack2{private Stack<Integer> stackData;private Stack<Integer> stackMin;public MyStack2(){this.stackData = new Stack<Integer>();this.stackMin = new Stack<Integer>();}public void push(int newNum){if (stackMin.isEmpty()){this.stackMin.push(newNum);}else if (newNum <= this.getMin()){this.stackMin.push(newNum);}else{int newMin = this.stackMin.peek();this.stackMin.push(newMin);}this.stackData.push(newNum);}public int getMin(){if (this.stackData.isEmpty()){throw new RuntimeException("Your stack is empty");}return this.stackMin.peek();}public int pop(){if (this.stackData.isEmpty()){throw new RuntimeException("Your stack is empty");}this.stackMin.pop();return this.stackData.pop();}}public static void main(String[] args){/*MyStack1 myStack1 = new MyStack1();Scanner scanner = new Scanner(System.in);int n = Integer.parseInt(scanner.nextLine());for (int i = 1; i <= n; i++){String[] inputData = scanner.nextLine().split(" ");if (inputData[0].equals("push")){myStack1.push(Integer.parseInt(inputData[1]));}else if (inputData[0].equals("pop")){myStack1.pop();}else if (inputData[0].equals("getMin")){System.out.println(myStack1.getMin());}}scanner.close();*/MyStack2 myStack2 = new MyStack2();Scanner scanner = new Scanner(System.in);int n = Integer.parseInt(scanner.nextLine());for (int i = 1; i <= n; i++){String[] inputData = scanner.nextLine().split(" ");if (inputData[0].equals("push")){myStack2.push(Integer.parseInt(inputData[1]));}else if (inputData[0].equals("pop")){myStack2.pop();}else if (inputData[0].equals("getMin")){System.out.println(myStack2.getMin());}}scanner.close();}}
CD6由两个栈组成的队列
描述
用两个栈实现队列，支持队列的基本操作。
输入描述：
第一行输入一个整数N，表示对队列进行的操作总数。
下面N行每行输入一个字符串S，表示操作的种类。
如果S为"add"，则后面还有一个整数X表示向队列尾部加入整数X。
如果S为"poll"，则表示弹出队列头部操作。
如果S为"peek"，则表示询问当前队列中头部元素是多少。
输出描述：
对于每一个为"peek"的操作，输出一行表示当前队列中头部元素是多少。
示例1
输入：
6add 1add 2add 3peekpollpeek输出：
12备注：
1<=N<=1000000-1000000<=X<=1000000数据保证没有不合法的操作
解答
import java.util.Scanner;import java.util.Stack;public class Main{public static class TwoStacksQueue{// 定义两个栈StackPush\ StackPoppublic Stack<Integer> StackPush;public Stack<Integer> StackPop;// 构造函数public TwoStacksQueue(){this.StackPush = new Stack<Integer>();this.StackPop = new Stack<Integer>();}// pushToPop函数// 两个前提条件： stackPop非空才能倒入， stackPush必须倒完public void pushToPop(){if (this.StackPop.isEmpty()){while (!this.StackPush.isEmpty()){this.StackPop.push(this.StackPush.pop());}}}// add函数public void add(int x){this.StackPush.push(x);pushToPop();}// poll函数public int poll(){// 如果栈都为空则报错if (this.StackPush.isEmpty() && this.StackPop.isEmpty()){throw new RuntimeException("Your queue is empty");}pushToPop();return this.StackPop.pop();}// peek函数public int peek(){if (this.StackPush.isEmpty() && this.StackPop.isEmpty()){throw new RuntimeException("Your queue is empty");}pushToPop();return this.StackPop.peek();}}public static void main(String[] args) {TwoStacksQueue queue = new TwoStacksQueue();Scanner scanner = new Scanner(System.in);int n = Integer.parseInt(scanner.nextLine());for (int i = 1; i <= n; i++){String[] inputData = scanner.nextLine().split(" ");if (inputData[0].equals("add")){queue.add(Integer.parseInt(inputData[1]));}else if (inputData[0].equals("poll")){queue.poll();}else if (inputData[0].equals("peek")){System.out.println(queue.peek());}}scanner.close();}}
CD7用递归函数和栈逆序一个栈
描述
一个栈依次压入1,2,3,4,5，那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后，从栈顶到栈底为1,2,3,4,5，也就是实现栈中元素的逆序，但是只能用递归函数来实现，不能用其他数据结构。
输入描述：
输入数据第一行一个整数N为栈中元素的个数。
接下来一行N个整数X_iX**i表示一个栈依次压入的每个元素。
输出描述：
输出一行表示栈中元素逆序后的栈顶到栈底的每个元素
示例1
输入：
51 2 3 4 5输出：
1 2 3 4 5
解答
import java.util.Scanner;import java.util.Stack;public class Main{// 递归函数一：将栈底的元素返回并移除public static int getAndRemoveLastElement(Stack<Integer> stack){// 记录位置方便递归int x = stack.pop();if (stack.isEmpty()){return x;}else{int last = getAndRemoveLastElement(stack);stack.push(x); // 恢复原来顺序return last;}}public static void reverse(Stack<Integer> stack){if (stack.isEmpty()){return ;}int x = getAndRemoveLastElement(stack);reverse(stack);stack.push(x);}public static void main(String[] args){Stack<Integer> stack = new Stack<>();Scanner scanner = new Scanner(System.in);int n = Integer.parseInt(scanner.nextLine());for (int i = 1; i <= n; i++){int x = scanner.nextInt();stack.push(x);}reverse(stack);while (!stack.isEmpty()){System.out.print(stack.pop() + " ");}System.out.println();}}
CD13用一个栈实现另一个栈的排序
描述
一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？
输入描述：
第一行输入一个N，表示栈中元素的个数
第二行输入N个整数a_ia**i表示栈顶到栈底的各个元素
输出描述：
输出一行表示排序后的栈中栈顶到栈底的各个元素。
示例1
输入：
55 8 4 3 6输出：
8 6 5 4 3备注：
1 <= N <= 10000
-1000000 <= a_nan <= 1000000
代码
import java.util.Scanner;import java.util.Stack;public class Main{// 要排序的栈为stack, 辅助栈为help, 在stack栈进行pop操作，弹出的元素记作cur// 分两种情况讨论： 1、 cur <= help栈顶元素， 则将cur直接压入help栈中// 2、 cur > help栈顶元素 stack.push(help.pop())直到cur <= help栈顶元素位置， 最后把cur压入help中public static void sortStackByStack(Stack<Integer> stack){Stack<Integer> help = new Stack<>();while (!stack.isEmpty()){int cur = stack.pop();while (!help.isEmpty() && cur > help.peek()){stack.push(help.pop());}help.push(cur);}while (!help.isEmpty()){stack.push(help.pop());}}public static void main(String[] args){Scanner scanner = new Scanner(System.in);Stack<Integer> stack = new Stack<>();int n = Integer.valueOf(scanner.nextLine());// 读入待排序数据for (int i = 0; i < n; i++){int x = scanner.nextInt();stack.push(x);}sortStackByStack(stack);// 输出Stack中排好序的结果while (!stack.isEmpty()){System.out.print(stack.pop() + " ");}System.out.println();}}
CD15生成窗口最大值数组
描述
有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置，求每一种窗口状态下的最大值。（如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值）
输入描述：
第一行输入n和w，分别代表数组长度和窗口大小
第二行输入n个整数X_iX**i，表示数组中的各个元素
输出描述：
输出一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值
示例1
输入：
8 34 3 5 4 3 3 6 7输出：
5 5 5 4 6 7说明：
例如，数组为[4，3，5，4，3，3，6，7]，窗口大小为3时：[4 3 5] 4 3 3 6 7 窗口中最大值为54 [3 5 4] 3 3 6 7 窗口中最大值为54 3 [5 4 3] 3 6 7 窗口中最大值为54 3 5 [4 3 3] 6 7 窗口中最大值为44 3 5 4 [3 3 6] 7 窗口中最大值为64 3 5 4 3 [3 6 7] 窗口中最大值为7输出的结果为{5 5 5 4 6 7}备注：
1\le w \le n \le 10000001≤w≤n≤1000000-1000000 \le X_i \le 1000000−1000000≤Xi≤1000000
解答
import java.util.LinkedList;import java.util.Scanner;public class Main{public static int[] getMaxWindow(int[] arr, int w){// 检验参数是否有效if (arr == null && w < 1 && arr.length < w){return null;}LinkedList<Integer> qmax = new LinkedList<>();int[] res = new int[arr.length - w + 1];int index = 0;for (int i = 0; i < arr.length; i++){while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i] ){qmax.pollLast();}qmax.addLast(i);// {0, 1,} 2, 3, 4... w = 2// 当 i = 2时， 0出队 也就是 i - w == qmax.peekFirst() 队首元素出队// qmax要溢出时， 队首元素出队if (qmax.peekFirst() == i - w){qmax.pollFirst();}if (i >= w - 1){// 至少检索了w个元素后，才能把队首元素下标对应值放入res数组中res[index++] = arr[qmax.peekFirst()];}}return res;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String[] inputData = scanner.nextLine().split(" ");int len = Integer.parseInt(inputData[0]);int w = Integer.parseInt(inputData[1]);int[] arr = new int[len];int[] res = new int[len - w + 1];int i = 0;for (i = 0; i < len; i++){int x = scanner.nextInt();arr[i] = x;}res = getMaxWindow(arr, w);for (i = 0; i < res.length; i++){System.out.print(res[i] + " ");}System.out.println();}}
CD101单调栈结构
描述
给定一个不含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。
输入描述：
第一行输入一个数字 n，表示数组 arr 的长度。
以下一行输出 n个数字，表示数组的值。
输出描述：
输出n行，每行两个数字 L 和 R，如果不存在，则值为-1，下标从0开始。
示例1
输入：
73 4 1 5 6 2 7复制
输出：
-1 20 2-1 -12 53 52 -15 -1复制
备注：
1 \le n \le 10000001≤n≤1000000-1000000 \le arr_i \le 1000000−1000000≤arri≤1000000
解答
import java.util.Scanner;import java.util.Stack;public class Main{public static int[][] rightWay(int[] arr){int[][] res = new int[arr.length][2];for (int i = 0; i < arr.length; i++){int leftLessIndex = -1;int rightLessIndex = -1;int cur = i - 1;while (cur >= 0){if (arr[cur] < arr[i]){leftLessIndex = cur;break;}cur--;}cur = i + 1;while (cur < arr.length){if (arr[cur] < arr[i]){rightLessIndex = cur;break;}cur++;}res[i][0] = leftLessIndex;res[i][1] = rightLessIndex;}return res;}public static int[][] getNearLessNoRepeat(int[] arr){int[][] res = new int[arr.length][2];Stack<Integer> stack = new Stack<>();for (int i = 0; i < arr.length; i++){while (!stack.isEmpty() && arr[stack.peek()] > arr[i]){int index = stack.pop();int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();int rightLessIndex = i;res[index][0] = leftLessIndex;res[index][1] = rightLessIndex;}stack.push(i);}while (!stack.isEmpty()){int popIndex = stack.pop();res[popIndex][1] = -1; // 结算阶段rightLessIndex为-1， 因为没有数使它们弹出res[popIndex][0] = stack.isEmpty() ? -1 : stack.peek();// 判断弹出的数下面有没有数， 如果没有rightLessIndex为-1； 如果有则为下面数的下标}return res;}public static void main(String[] args) {Scanner s = new Scanner(System.in);int n = Integer.parseInt(s.nextLine());int[] arr = new int[n];for (int i = 0; i < n; i++){arr[i] = s.nextInt();}// int[][] res = rightWay(arr);int[][] res = getNearLessNoRepeat(arr);for (int i = 0; i < res.length; i++){System.out.println(res[i][0] + " " + res[i][1]);}}}
CD188单调栈结构(进阶)
描述
给定一个可能含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。
输入描述：
第一行输入一个数字 n，表示数组 arr 的长度。
以下一行输入 n 个数字，表示数组的值
输出描述：
输出n行，每行两个数字 L 和 R，如果不存在，则值为 -1，下标从 0 开始。
示例1
输入：
73 4 1 5 6 2 7输出：
-1 20 2-1 -12 53 52 -15 -1备注：
1 \leq n \leq 10000001≤n≤1000000-1000000 \leq arr_i \leq 1000000−1000000≤arri≤1000000
解答
import java.util.ArrayList;import java.util.List;import java.util.Scanner;import java.util.Stack;public class Main{public static int[][] getNearLess(int[] arr){int[][] res = new int[arr.length][2];Stack<List<Integer>> stack = new Stack<>();for (int i = 0; i < res.length; i++){while (!stack.isEmpty() && arr[i] < arr[stack.peek().get(0)]){List<Integer> popList = stack.pop();// 取出位于下面的列表中，最晚加入的那个int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);for (Integer x : popList){res[x][0] = leftLessIndex;res[x][1] = i;}}// 当前数比stack栈顶数相等if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]){stack.peek().add(i);}else{// 当前数比stack栈顶数大或者此时为空栈ArrayList<Integer> list = new ArrayList<>();list.add(i);stack.push(list);}}while (!stack.isEmpty()){List<Integer> popList = stack.pop();int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);for (Integer x : popList){res[x][0] = leftLessIndex;res[x][1] = -1;}}return res;}public static void main(String[] args) {Scanner s = new Scanner(System.in);int n = Integer.parseInt(s.nextLine());int[] arr = new int[n];String[] str = s.nextLine().split(" ");for (int i = 0; i < n; i++){arr[i] = Integer.parseInt(str[i]);}int[][] res = getNearLess(arr);for (int i = 0; i < res.length; i++){System.out.println(res[i][0] + " " + res[i][1]);}}}
第二章 链表问题
CD48打印两个升序链表的公共部分
描述
给定两个升序链表，打印两个升序链表的公共部分。
输入描述：
第一个链表的长度为 n。
第二个链表的长度为 m。
链表结点的值为 val。
输出描述：
输出一行整数表示两个升序链表的公共部分的值 (按升序输出)。
示例1
输入：
41 2 3 451 2 3 5 6输出：
1 2 3备注：
1 \le n,m\le 10000001≤n,m≤1000000INTMIN \le val \le INTMAXINTMIN≤val≤INTMAX
解答
import java.util.Scanner;public class Main{public static class Node{public int value;public Node next;public Node(int v){this.value = v;}}public static void printCommonPart(Node head1, Node head2){while (head1 != null && head2 != null){if (head1.value > head2.value){head2 = head2.next;}else if (head1.value < head2.value){head1 = head1.next;}else{System.out.print(head1.value + " ");head1 = head1.next;head2 = head2.next;}}System.out.println();}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int m = 0, n = 0;m = Integer.parseInt(scanner.nextLine());Node head1 = new Node(scanner.nextInt());Node cur = head1;for (int i = 1; i < m; i++){cur.next = new Node(scanner.nextInt());cur = cur.next;}scanner.nextLine();n = Integer.parseInt(scanner.nextLine());Node head2 = new Node(scanner.nextInt());cur = head2;for (int i = 1; i < n; i++){cur.next = new Node(scanner.nextInt());cur = cur.next;}printCommonPart(head1, head2);}}
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dqnppjTG-1642684708381)(C:\Users\lenovo\AppData\Roaming\Typora\typora-user-images\image-2029210416383.png)]
CD49在链表中删除倒数第K个节点
描述
给出一个单链表，返回删除单链表的倒数第 K 个节点后的链表。
输入描述：
第一行输入两个正整数 n, K ，分别表示链表的长度和要删除单链表倒数第K个节点。 接下来一行有 n 个整数，依次表示单链表中的各个节点的节点值val。
输出描述：
在给定的函数内返回删除倒数第K个节点后的链表的头指针。
示例1
输入：
5 41 2 3 4 5输出：
1 3 4 5备注：
1 \le K \le n \le 10000001≤K≤n≤1000000-1000000 \le val \le 1000000−1000000≤val≤1000000
解答
import java.util.Scanner;public class Main{public static class Node{public int value;public Node next;public Node(int value){this.value = value;}}public static Node removeLastNode(Node head, int i){if (head == null || i < 1){return head;}Node cur = head;while (cur != null){i--;cur = cur.next;}if (i > 0){// i > 0 不用调整链表}else if (i == 0){// 要删除头结点head = head.next;}else{cur = head;i++;while (i != 0){i++;cur = cur.next;}cur.next = cur.next.next;}return head;}public static void main(String[] args) {Scanner s = new Scanner(System.in);int m = s.nextInt(), k = s.nextInt();s.nextLine();Node head1 = new Node(s.nextInt());Node cur = head1;for (int i = 1; i < m; i++){cur.next = new Node(s.nextInt());cur = cur.next;}removeLastNode(head1, k);cur = head1;while (cur != null){System.out.print(cur.value + " ");cur = cur.next;}System.out.println();}}
CD106删除链表的中间节点
描述
给定一个链表，实现删除链表第 K 个节点的函数。
输入描述：
n 表示链表的长度。
m 表示删除链表第几个节点。
val 表示链表节点的值。
输出描述：
在给定的函数中返回链表的头指针。
示例1
输入：
5 31 2 3 4 5输出：
1 2 4 5备注：
1 \le K \le n \le 10000001≤K≤n≤1000000-1000000 \le val \le 1000000−1000000≤val≤1000000
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NlfKmD2M-1642684708385)(C:\Users\lenovo\Desktop\资源\IMG_2029_224721.jpg)]
解答
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Scanner;public class Main{public static class Node{public int value;public Node next;public Node(int v){this.value = v;}}/*public static Node removeMidNode(Node head){if (head == null || head.next == null){return head;}if (head.next.next == null){return head.next;}Node slow = head;Node fast = head.next.next;// 使用快慢指针法 快指针一次走两步，慢指针一次走一步// fast , slow = head 初始化// fast->next == null || fast->next->next == null 时 slow 指针为要删除的那个// 因此 fast初始化要改成fast = head->next->next;while (fast.next != null && fast.next.next != null){fast = fast.next.next;slow = slow.next;}slow.next = slow.next.next;return head;}public static Node removeByRatio(Node head, int a, int b){// 我们假设链表的节点总数为n// 我们要删除的节点 (double) a * (double) n / (double) b 然后再向上取整if (a < 1 || a > b){// 分母比1小 或者 分数>1 为非法参数return null;}int n = 0;Node cur = head;while (cur != null){n++;cur = cur.next;}n = (int) Math.ceil((double)(a * n) / (double) (b));if (n == 1){head = head.next;}else if (n > 1){cur = head;n--;while (n > 1){cur = cur.next;n--;}cur.next = cur.next.next;}return head;}public static void main(String[] args) {// 实例输入// 5// 1 2 3 4 5//输出// 1 2 4 5Scanner s = new Scanner(System.in);int m = Integer.parseInt(s.nextLine());Node head = new Node(s.nextInt());Node cur = head;for (int i = 1; i < m; i++){cur.next = new Node(s.nextInt());cur = cur.next;}// removeMidNode(head);// 链表为1->2->3->4->5// a = 1 b = 3 删除第二个节点// 输出 1->3->4->5s.nextLine();int a = s.nextInt(), b = s.nextInt();removeByRatio(head, a, b);cur = head;while (cur != null){System.out.print(cur.value + " ");cur = cur.next;}System.out.println();}*/public static Node removeKNode(Node head, int k){if (head == null || k < 1){return head;}if (k == 1){return head.next;}Node cur = head;k--;while (k > 1){cur = cur.next;k--;}cur.next = cur.next.next;return head;}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader( System.in ) );String[] inputData = br.readLine().trim().split(" ");int n = Integer.parseInt(inputData[0]), k = Integer.parseInt(inputData[1]);inputData = br.readLine().trim().split(" ");Node head = new Node(Integer.parseInt(inputData[0]));Node cur = head;for (int i = 1; i < n; i++){cur.next = new Node(Integer.parseInt(inputData[i]));cur = cur.next;}removeKNode(head, k);cur = head;while (cur != null){System.out.print(cur.value + " ");cur = cur.next;}System.out.println();}}
CD107反转单向链表
描述
实现反转单向链表和双向链表的函数。
如 1->2->3 反转后变成 3->2->1。
输入描述：
第一行一个整数 n，表示单链表的长度。
第二行 n 个整数 val 表示单链表的各个节点。
第三行一个整数 m，表示双链表的长度。
第四行 m 个整数 val 表示双链表的各个节点。
输出描述：
在给定的函数内返回相应链表的头指针。
示例1
输入：
31 2 341 2 3 4输出：
3 2 14 3 2 1备注：
1 \le n,m\le10000001≤n,m≤1000000-1000000 \le val \le 1000000−1000000≤val≤1000000
解答
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main{public static class Node{public int value;public Node next;public Node(int value){this.value = value;}}public static class DoubleNode{public int value;public DoubleNode last;public DoubleNode next;public DoubleNode(int v){this.value = v;}}public static Node reverseList(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 reverseDoubleNodeList(DoubleNode head){DoubleNode pre = null;DoubleNode next = null;while (head != null){next = head.next;head.last = next;head.next = pre; // 通过这两步head节点完成了反转pre = head;head = next;}return pre; // 注意输出是pre不是head}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] inputData = br.readLine().trim().split(" ");int m = Integer.parseInt(inputData[0]);inputData = br.readLine().trim().split(" ");Node head1 = new Node(Integer.parseInt(inputData[0]));Node cur = head1;for (int i = 1; i < m; i++){cur.next = new Node(Integer.parseInt(inputData[i]));cur = cur.next;}inputData = br.readLine().trim().split(" ");int n = Integer.parseInt(inputData[0]);inputData = br.readLine().trim().split(" ");DoubleNode head2 = new DoubleNode(Integer.parseInt(inputData[0]));DoubleNode pre = null, current = head2, next = null;for (int i = 1; i < n; i++){current.next = new DoubleNode(Integer.parseInt(inputData[i]));current.last = pre;pre = current;current = current.next;next = current.next;}head1 = reverseList(head1);head2 = reverseDoubleNodeList(head2);cur = head1;while (cur != null){System.out.print(cur.value + " ");cur = cur.next;}System.out.println();current = head2;while (current != null){System.out.print(current.value + " ");current = current.next;}System.out.println();}}
CD108反转部分单向链表
描述
给定一个单链表，在链表中把第 L 个节点到第 R 个节点这一部分进行反转。
输入描述：
n 表示单链表的长度。
val 表示单链表各个节点的值。
L 表示翻转区间的左端点。
R 表示翻转区间的右端点。
输出描述：
在给定的函数中返回指定链表的头指针。
示例1
输入：
51 2 3 4 51 3输出：
3 2 1 4 5备注：
1 \le n \le 10000001≤n≤10000001 \leq L \leq R \leq n1≤L≤R≤n-1000000 \le val \le 1000000−1000000≤val≤1000000
解答
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main{public static class Node{public int value;public Node next;public Node(int value){this.value = value;}}public static Node reversePart(Node head, int from, int to){int len = 0;Node cur = head;Node fromPre = null, toNext = null;while (cur != null){len++;fromPre = (len == from - 1) ? cur : fromPre; // 找到反转部分的头结点前面一个节点toNext = (len == to + 1) ? cur : toNext; // 找到反转部分的头结点后面一个节点cur = cur.next;}if (from > to || from < 1 || to > len){// 不满足题目 1<=from<=to<=N的条件，返回头结点return head;}Node node1 = (fromPre == null) ? head : fromPre.next;Node node2 = node1.next;node1.next = toNext;Node next = null;while (node2 != toNext){next = node2.next;node2.next = node1;node1 = node2;node2 = next;}if (fromPre != null){fromPre.next = node1;return head;}else{return node1;}}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] inputData = br.readLine().trim().split(" ");int m = Integer.parseInt(inputData[0]);inputData = br.readLine().trim().split(" ");Node head = new Node(Integer.parseInt(inputData[0]));Node cur = head;for (int i = 1; i < m; i++){cur.next = new Node(Integer.parseInt(inputData[i]));cur = cur.next;}inputData = br.readLine().trim().split(" ");int from = Integer.parseInt(inputData[0]), to = Integer.parseInt(inputData[1]);head = reversePart(head, from, to);cur = head;while (cur != null){System.out.print(cur.value + " ");cur = cur.next;}System.out.println();}}
CD111判断一个链表是否为回文结构
描述
给定一个链表，请判断该链表是否为回文结构。
输入描述：
n 表示链表的长度
ai 表示链表的各个节点的值。
输出描述：
如果为回文结构输出 “true” , 否则输出 “false”。
示例1
输入：
41 2 2 1输出：
true备注：
1 \le n \le 10000001≤n≤1000000-1000000 \le a_i \le 1000000−1000000≤ai≤1000000
解答
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Stack;public class Main{public static class Node{public int value;public Node next;public Node(int v){this.value = v;}}public static boolean isPalindrome1(Node head){Stack<Integer> stack = new Stack<>();Node cur = head;while (cur != null){stack.push(cur.value);cur = cur.next;}cur = head;while (cur != null){if (cur.value != stack.pop()){return false;}cur = cur.next;}return true;}public static boolean isPalindrome2(Node head){if (head == null || head.next == null){return true;}// 利用快慢指针方法将链表右半部分放入栈中和链表左半部分比较Node fast = head, slow = head.next; // 注意慢指针slow = head.next; 通过画图得到规律Stack<Node> stack = new Stack<>();// !!! 我第一次做题把fast.next != null && fast.next.next != null顺序反过来了，// 出现了空指针异常的报错while (fast.next != null && fast.next.next != null){fast = fast.next.next;slow = slow.next;}while (slow != null){stack.push(slow);slow = slow.next;}while (! stack.isEmpty()){if (stack.pop().value != head.value){return false;}head = head.next;}return true;}public static void main(String[] args) throws IOException, NullPointerException{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] inputData = br.readLine().trim().split(" ");int m = Integer.parseInt(inputData[0]);inputData = br.readLine().trim().split(" ");Node head = new Node(Integer.parseInt(inputData[0]));Node cur = head;for (int i = 1; i < m; i++){cur.next = new Node(Integer.parseInt(inputData[i]));cur = cur.next;}// System.out.println(isPalindrome1(head));System.out.println(isPalindrome2(head));}}
CD112判断一个链表是否为回文结构(进阶)
描述
给定一个链表，请判断该链表是否为回文结构。
输入描述：
n 表示链表的长度。
ai 表示链表节点的值
输出描述：
如果为回文结构输出 “true” , 否则输出 “false”。
示例1
输入：
51 2 3 2 1输出：
true备注：
1 \le n \le 20000001≤n≤2000000-1000000 \le a_i \le 1000000−1000000≤ai≤1000000
解答
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main{public static class Node{public int value;public Node next;public Node (int value){this.value = value;}}public static boolean isPalindromePlus(Node head){if (head == null || head.next == null){return true;}Node node1 = head, node2 = head; // node1为快指针，node2为慢指针while (node1.next != null && node1.next.next != null){node1 = node1.next.next;node2 = node2.next;}// 此时node1到了最后, node2到了中间（后半段开头在node2+1节点处）node1 = node2.next;node2.next = null;Node node3 = null;while (node1 != null){node3 = node1.next;node1.next = node2;node2 = node1;node1 = node3;}// node2为最后一个节点node3 = node2; // 保存最后一个节点node1 = head;boolean res = true;while (node1 != null && node2 != null){if (node1.value != node2.value){res = false;break;}node1 = node1.next;node2 = node2.next;}// 恢复原来的链表node1 = node3.next;node3.next = null;while(node1 != null){node2 = node1.next;node1.next = node3;node3 = node1;node1 = node2;}return res;}public static void main(String[] args) throws IOException, NullPointerException{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] inputData = br.readLine().trim().split(" ");int m = Integer.parseInt(inputData[0]);inputData = br.readLine().trim().split(" ");Node head = new Node(Integer.parseInt(inputData[0]));Node cur = head;for (int i = 1; i < m; i++){cur.next = new Node(Integer.parseInt(inputData[i]));cur = cur.next;}// System.out.println(isPalindrome1(head));System.out.println(isPalindromePlus(head));}}
