整数
一、整数反转_7
/* 12345 变成 54321 */ public class 整数反转_7 { public static void main(String[] args){ int x = 12345; System.out.println(reverseInt(x)); } public static int reverseInt(int x){ int res = 0; while (x != 0){ int pop = x % 10; if (res > Integer.MAX_VALUE / 10 || res == Integer.MAX_VALUE && pop > 7) return 0; if (res < Integer.MIN_VALUE / 10 || res == Integer.MIN_VALUE && pop < -8) return 0; res = res * 10 + pop; x /= 10; } return res; } }
数组
一、两数之和_1(数组）
/* 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] */ import java.util.HashMap; import java.util.Map; public class 两数之和_1 { public static void main(String[] args){ int[] nums = {1,2}; int target = 3; //法一： int[] result = method1(nums,target); System.out.println( result[0] + "" + result[1] ); //法二： int[] result2 = method2(nums,target); System.out.println(result2[0] + "" + result2[1]); } //法一：两次遍历，时间O(n2)，空间O(n) public static int[] method1(int[] nums, int target){ for (int i = 0; i < nums.length; i++){ for (int j = i+1; j < nums.length; j++){ if (nums[i] + nums[j] == target){ return new int[] {i,j}; } } } throw new IllegalArgumentException("No such target"); } //法二：采用字典存储,时间O（n),空间O(n） public static int[] method2 (int[] nums, int target){ //遍历一遍，存储到map中，key为nums值，value为索引 Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; i++){ map.put(nums[i] , i); } // 遍历第二遍，查看target-nums[i] 是否在字典中 for (int i = 0; i < nums.length; i++){ int tmp = target - nums[i]; if (map.containsKey(tmp) && map.get(tmp) != i) { return new int[]{i, map.get(tmp)}; } } throw new IllegalArgumentException("No such target!"); } }
二、三数之和_15（数组）
/* 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ] */ import java.util.Arrays; import java.util.ArrayList; import java.util.List; public class 三数之和_15 { public static void main(String[] args){ int[] nums = {-1,0,1,2,-2,4}; threeSum(nums); } public static List<List<Integer>> threeSum(int[] nums){ List<List<Integer>> ans = new ArrayList<List<Integer>>(); int len = nums.length; if (nums == null && len < 3) return ans; Arrays.sort(nums); // 排序 for (int i = 0; i < len; i++){ if (nums[0] > 0) break; //如果第一个数大于0，直接退出 while (i > 0 && nums[i] == nums[i-1]) continue; //去重 int L = i+1, R = len - 1; while (L < R){ //两数之和 int sum = nums[i] + nums[L] + nums[R]; if (sum == 0){ ans.add(Arrays.asList(nums[i],nums[L],nums[R])); while (L < R && nums[L] == nums[L+1]) L++; //去重 while (L < R && nums[R] == nums[R-1]) R--; //去重 L++; R--; } else if(sum < 0) { L++; } else if (sum > 0){ R--; } } } return ans; } }
三、删除排序数组中的重复项_26 (数组）
/* 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。 示例 1: 给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。 示例 2: 给定 nums = [0,0,1,1,1,2,2,3,3,4], 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。 你不需要考虑数组中超出新长度后面的元素。 */ public class 删除排序数组中的重复项_26 { public static void main(String[] args){ int[] nums = {1,1,1,2,2,3,4,4,5}; System.out.println(removeDulplicates(nums)); } public static int removeDulplicates(int[] nums){ if (nums.length == 0) return 0; int i = 0; for (int j = 1; j < nums.length; j++){ if (nums[i] != nums[j]){ i++; nums[i] = nums[j]; } } return i+1; } }
四、寻找两个有序数组的中位数_4（数组）
/* 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例 1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0 示例 2: nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5 */ public class 寻找两个有序数组的中位数_4 { public static void main(String[] arg){ int[] nums1 = {}; int[] nums2 = {2,3}; System.out.println(findMedianSortedArrays(nums1,nums2)); } public static double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; int[] numsAll = new int[ m+n ]; int i = 0; int j = 0; while (i < m && j < n){ if (nums1[i] < nums2[j]){ numsAll[i+j] = nums1[i]; i++; } else{ numsAll[i+j] = nums2[j]; j++; } } for (int a=i+j; a < m+n; a++ ){ if (i < m){ numsAll[a] = nums1[i]; i++; } else{ numsAll[a] = nums2[j]; j++; } } int mid = (m+n)/2; if ((m+n)%2 == 0){ return (numsAll[mid-1] + numsAll[mid]) / 2.0; } else{ return numsAll[mid]; } } }
五、搜索插入位置_35（数组）
/* 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。 示例 1: 输入: [1,3,5,6], 5 输出: 2 示例 2: 输入: [1,3,5,6], 2 输出: 1 示例 3: 输入: [1,3,5,6], 7 输出: 4 示例 4: 输入: [1,3,5,6], 0 输出: 0 */ public class 搜索插入位置_35 { public static void main(String[] args){ int[] nums = {1,2,5,7}; int target = 2; searchInsert(nums,target); } public static int searchInsert(int[] nums, int target) { int len = nums.length; if (len <= 0) return 0; if (nums[len-1] < target) return len; int left = 0 , right = len - 1; while (left <= right){ int mid = (left + right) / 2; if (nums[mid] > target){ right = mid - 1; } else if (nums[mid] < target){ left = mid + 1; } else{ return mid; } } return left; } }
六、杨辉三角_118 （二维数组）
import java.util.ArrayList; import java.util.List; public class 杨辉三角_118 { public static void main(String[] args){ int numRows = 5; generate(numRows); } public static List<List<Integer>> generate(int numRows){ List<List<Integer>> triangle = new ArrayList<List<Integer>> (); if (numRows == 0) return triangle; triangle.add(new ArrayList<Integer>()); triangle.get(0).add(1); for (int i= 1; i < numRows; i++){ List<Integer> row = new ArrayList<>(); List<Integer> preRow = triangle.get(i - 1); row.add(1); for (int j = 1; j < i; j++){ row.add(preRow.get(j) + preRow.get(j-1)); } row.add(1); triangle.add(row); } return triangle; } }
七、盛最多水的容器_11（数组）
/* 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 输入: [1,8,6,2,5,4,8,3,7] 输出: 49 链接：https://leetcode-cn.com/problems/container-with-most-water。 思路： 两个首尾指针L,R，面积等于 高( tmp = min(nums[L],nums[R]) * 底 （R-L)； 然后，如果高等于nums[L]，则L++; 如果高等于nums[R], 则R--; */ public class 盛最多水的容器_11 { public static void main(String[] args){ int[] height = {1,8,6,2,5,4,8,3,7}; System.out.println(maxArea(height)); } public static int maxArea(int[] height){ int L = 0 , R = height.length - 1; int area = Integer.MIN_VALUE; while (L < R){ int temp = Math.min(height[L] , height[R]); area = Math.max(area, temp * (R - L)); if (temp == height[L]) L++; else if (temp == height[R]) R--; } return area; } }
八、买卖股票的最佳时机_121 (数组)
/* 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。 示例 1: 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 示例 2: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 思路：两个变量，一个记录谷底数值，一个记录结果（即最大利润）； */ public class 买卖股票的最佳时机_121 { public static void main(String[] args){ int[] prices = {7,1,5,6,4,3}; System.out.println(maxProfit(prices)); } public static int maxProfit(int[] prices) { int minPrice = Integer.MAX_VALUE; int maxProfit = 0; for (int i = 0; i < prices.length; i++){ if (prices[i] < minPrice){ minPrice = prices[i]; } else if (prices[i] - minPrice > maxProfit){ maxProfit = prices[i] - minPrice; } } return maxProfit; } }
九、189
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
说明 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。 要求使用空间复杂度为 O(1) 的 原地 算法。
class Solution{ public void rotate(int[] nums, int k) { k %= nums.length; reverse(nums,0,nums.length - 1); reverse(nums,0,k - 1); reverse(k,nums.length - 1); } public static void reverse(int[] nums, int start, int end) { while (start < end){ int tmp = nums[start]; nums[start] = nums[end]; nums[end] = tmp; start++; end--; } } }
字符串
一、Z型变换_6
import java.util.ArrayList; import java.util.List; public class Z字型变换_6 { public static void main(String[] args){ String s = "leetcodeishiring"; int numsRow = 3; System.out.println(convert(s,numsRow)); } public static String convert(String s,int numsRow){ if (s.length() < numsRow) return s; //初始化 List<StringBuilder> rows = new ArrayList<>(); for (int i = 0; i < Math.min(s.length(),numsRow); i++){ rows.add(new StringBuilder()); } int curRow = 0; boolean goingDown = false; for (char c:s.toCharArray()){ rows.get(curRow).append(c); if (curRow == 0 || curRow == numsRow - 1) goingDown = !goingDown; curRow += goingDown ? 1 : -1; } StringBuilder res = new StringBuilder(); for (StringBuilder row: rows){ res.append(row); } return res.toString(); } }
二、二进制求和_67
/* 1011 + 1101 = 11000 */ public class 二进制求和_67 { public static void main(String[] args){ String a = "1011", b = "1101"; System.out.println(addBinary(a,b)); } public static String addBinary(String a,String b){ StringBuilder ans = new StringBuilder(); int ca = 0; for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--){ int sum = ca; sum += (i >= 0) ? a.charAt(i) - '0' : 0; sum += (j >= 0) ? b.charAt(j) - '0' : 0; ca = sum / 2; ans.append(sum % 2); } ans.append(ca == 1 ? ca : ""); return ans.reverse().toString(); } }
三、唯一摩尔斯密码词_804
import java.util.HashMap; import java.util.Map; public class 唯一摩尔斯密码词_804 { public static void main(String[] args) { String[] pwd = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."}; String keys = "abcdefghijklmnopqrstuvwxyz"; char[] key = keys.toCharArray(); Map<String, Integer> map = new HashMap<>(); String[] words = {"gin", "zen", "gig", "msg"}; for (String word : words) { String password = ""; for (char ch : word.toCharArray()) { password += pwd[ch - 97]; } map.put(password, 1); } System.out.println(map.keySet().size()); } }
四、报数_38
/* 1 1 2 11 "一个1" 3 21 "一个2一个1" 4 1211 "一个2一个1" 5 111221 "一个1一个2两个1" 6 312211 */ public class 报数_38 { public static void main(String[] args){ int n = 4; System.out.println( countAndSay(n) ); } public static String countAndSay(int n) { String s = "11"; if (n==1){ return "1"; } else if(n==2){ return s; } for (int i = 2; i < n; i++ ){ int j = 0; StringBuilder num = new StringBuilder(); while (j < s.length()-1){ int count = 1; while (j < s.length()-1 && s.charAt(j) == s.charAt(j+1)){ count += 1; j++; } num.append(""+count).append(s.charAt(j)); j++; } if (s.charAt(s.length()-1) != s.charAt(s.length()-2) ){ num.append("1").append(s.charAt(s.length()-1)); } s = num.toString(); } return s; } }
五、无重复的最长子串_3
/* 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 */ import java.util.Collection; import java.util.HashMap; import java.util.Map; import java.util.Set; public class 无重复元素的最长子串_3 { public static void main(String[] args){ String s = "dvdf"; int res = lengthOfLongestSubstring(s); System.out.println(res); } public static int lengthOfLongestSubstring(String s) { Map<Character,Integer> map = new HashMap<> (); int start = -1; int res = 0; for (int i = 0; i < s.length(); i++){ if (map.containsKey(s.charAt(i))){ start = Math.max(start,map.get(s.charAt(i))); } res = Math.max(i - start,res); map.put(s.charAt(i),i); } return res; } }
六、转换成小写字母_709
/* 所有字符串都转成小写 */ public class 转换成小写字母_709 { public static void main(String[] args){ String s = "HeLLo"; System.out.println(toLowerCase(s)); } public static String toLowerCase(String str){ char[] cArray = str.toCharArray(); for(int i= 0; i<cArray.length; i++){ if (cArray[i] <= 'Z' && cArray[i]>='A') { cArray[i] = (char) (cArray[i] + 32); } } return String.valueOf(cArray); } }
七、验证回文串_125
/* 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明：本题中，我们将空字符串定义为有效的回文串。 示例 1: 输入: "A man, a plan, a canal: Panama" 输出: true 示例 2: 输入: "race a car" 输出: false */ public class 验证回文串_125 { public static void main(String[] args){ String s = "A man, a plan, a canal:Panama"; System.out.println(isPal1(s)); } public static boolean isPal1(String s){ int len = s.length(); s = s.toLowerCase(); int i = 0, j = len - 1; while (i < j){ while (!isAlpha(s.charAt(i))){ i++; if (i == len){ return true; } } while (!isAlpha(s.charAt(j))){ j--; } if (s.charAt(i)!= s.charAt(j)){ return false; } i++; j--; } return true; } public static boolean isAlpha(char c){ if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' &&c <= '9')){ return true; } return false; } }
八、
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
示例 1:
输入: s = "leetcode"
输出: false
示例 2:
输入: s = "abc"
输出: true
说明 如果你不使用额外的数据结构，会很加分。
//使用字符数组 class Solution{ public boolean isUnique(String astr) { char[] astrArray = astr.toCharArray(); Arrays.sort(astrArray); for (int i = 0; i < astrArray.length - 1; i++){ if (astrArray[i] == astrArray[i+1]){ return false; } } return true; } }
//不使用额外空间 class Solution{ public boolean isUnique(String astr){ for (int i = 0; i < astr.length() - 1; i++){ if (astr.insdexOf(astr.charAt(i),i+1) != -1 ){ return false; } } return true; } }
九、
字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。
示例1:
输入：s1 = "waterbottle", s2 = "erbottlewat" 输出：True 示例2:
输入：s1 = "aa", "aba" 输出：False
class Solution { public boolean isFlipedString(String s1, String s2) { if (s1.length() != s2.length()){ return false; } s1 += s1; return s1.contains(s2); } }
HashMap
一、有效的括号_20
/* 判断括号是否有效 */ import javax.swing.text.html.ListView; import java.util.HashMap; import java.util.Stack; public class 有效的括号_20 { private HashMap<Character,Character> mapping; public 有效的括号_20(){ this.mapping = new HashMap<Character, Character>(); this.mapping.put(')','('); this.mapping.put(']','['); this.mapping.put('}','{'); } public static void main(String[] args){ String s = "(()[])"; 有效的括号_20 res = new 有效的括号_20(); System.out.println(res.isValid(s)); } public boolean isValid(String s){ Stack<Character> stack = new Stack<>(); for (char ch : s.toCharArray()){ if (this.mapping.containsKey(ch)) { char popChar = stack.isEmpty() ? '#' : stack.pop(); if (popChar != this.mapping.get(ch)) { return false; } } else { stack.push(ch); } } return stack.isEmpty(); } }
HashSet
一、两个数组的交集_349
/* 给定两个数组，编写一个函数来计算它们的交集。 示例 1: 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2] 示例 2: 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出: [9,4] */ import java.util.Arrays; import java.util.HashSet; public class 两个数组的交集_349 { public static void main(String[] args){ int[] nums1 = {4,9,5}; int[] nums2 = {9,4,9,8,4}; intersection(nums1, nums2); } public static int[] intersection(int[] nums1, int[] nums2) { HashSet<Integer> set1 = new HashSet<>(); for (Integer i: nums1) set1.add(i); HashSet<Integer> set2 = new HashSet<>(); for (Integer i : nums2) set2.add(i); if (set1.size() < set2.size()) return helper(set1 ,set2); else return helper(set2,set1); } public static int[] helper(HashSet<Integer> set1 , HashSet<Integer> set2){ int[] ans = new int[set1.size()]; int idx = 0; set1.retainAll(set2); for (int i : set1){ ans[idx++] = i; } return Arrays.copyOf(ans,idx); } }
二、独一无二的出现次数_1207
public boolean uniqueOccurrences(int[] arr) { HashMap <Integer,Integer> map = new HashMap<>(); for (int i:arr){ if (map.containsKey(i)){ map.put(i,map.get(i)+1); }else{ map.put(i,1); } } Set<Integer> set = new HashSet<> (); for (int i : map.values()){ set.add(i); } return map.size() == set.size(); }
三、
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:
输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
示例2:
输入：[1, 1, 1, 1, 2]
输出：[1, 2]
提示：
链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { private Set<Integer> set = new HashSet<Integer>(); //注意：这里一定要设为私有，不然递归不会改变set的值。【即应为全局】 public ListNode removeDuplicateNodes(ListNode head) { if (head == null) return null; if (!set.contains(head.val)){ set.add(head.val); head.next = removeDuplicateNodes(head.next); return head; } else{ return removeDuplicateNodes(head.next); } } }
四、回文排列
给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词。
示例1：
输入："tactcoa"
输出：true（排列有"tacocat"、"atcocta"，等等）
//每个字符出现的次数为偶数, 或者有且只有一个字符出现的次数为奇数时, 是回文的排列; 否则不是. //https://leetcode-cn.com/problems/palindrome-permutation-lcci/solution/li-yong-ha-xi-biao-by-jiangzs/ class Solution { public boolean canPermutePalindrome(String s) { Set<Character> set = new HashSet<>(); for (char c : s.toCharArray()) { if (!set.add(c)) { set.remove(c); } } return set.size() <= 1; } }
链表
一、两数相加_2
/* 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例： 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807 */ import java.util.ArrayList; class ListNode{ int val; ListNode next; ListNode(int x){ val = x; } } public class 两数相加_2 { public static void main(String[] args) { ListNode l1 = new ListNode(1); ListNode head1 = l1; for (int i = 2; i < 5; i++){ l1.next = new ListNode(i); l1 = l1.next; } ListNode l2 = new ListNode(3); ListNode head2 = l2; for (int i = 4; i < 6; i++){ l2.next = new ListNode(i); l2 = l2.next; } ArrayList<Integer> list = new ArrayList<Integer> (); ListNode res = addNum(head1,head2); while (res != null){ list.add(res.val); res = res.next; } list.stream().forEach(System.out::println); } public static ListNode addNum (ListNode l1 , ListNode l2){ ListNode res = new ListNode(0); ListNode head = res; int flag = 0; while (l1 != null || l2 != null){ int x = (l1 != null) ? l1.val : 0; int y = (l2 != null) ? l2.val : 0; int sum = x + y + flag; flag = sum / 10; res.next = new ListNode(sum % 10); res = res.next; if (l1 != null) l1 = l1.next; if (l2 != null) l2 = l2.next; } if (flag > 0){ res.next = new ListNode(flag); } return head.next; } }
二、回文链表
编写一个函数，检查输入的链表是否是回文的。
示例 1：
输入： 1->2
输出： false
示例 2：
输入： 1->2->2->1
输出： true
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) return true; boolean isodd = true; Stack<Integer> stack = new Stack<Integer>(); ListNode slow = head; ListNode fast = head; //快慢指针，并将前半值入栈 while (fast != null && fast.next != null) { stack.push(slow.val); slow = slow.next; fast = fast.next.next; if (fast == null) { isodd = false; } } //如果是奇数，则慢指针还要走一步 if (isodd) slow = slow.next; while (!stack.isEmpty()){ //出栈，判断后半部分和出栈值相同？ if ( stack.pop() != slow.val){ return false; } slow = slow.next; } return true; } }