LeetCode算法刷题录

public int maxSubArray(int[] nums) {
       int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 遍历数组，将元素相加，若>0加入结果集，否则重置。
            nums[i] += Math.max(nums[i - 1], 0);  
            // 将最新和值赋值nums数组，减少空间消费。
            res = Math.max(res, nums[i]); 
        }
        return res;
    }

public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target-nums[i])){ 
                //本来想着应该先遍历一次存储nums数组元素到map中，其实不必要，一次遍历即可，
                //不存在再push， 否则判断另一元素是否也在，在遍历完一遍后，必然可以所有元素都存在map中。
                return new int[]{i,map.get(target-nums[i])};
            }
            map.put(nums[i],i);
        }
        return new int[0];
    }

public void merge(int[] nums1, int m, int[] nums2, int n) {
        int len = m + n - 1;
        int len1 = m - 1, len2 = n - 1;
        while (len1 >= 0 && len2 >= 0) {
            nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
        }
        // 表示将nums2数组从下标0位置开始，拷贝到nums1数组中，从下标0位置开始，长度为len2+1
        System.arraycopy(nums2, 0, nums1, 0, len2 + 1);
    }

public int search(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int mid = i + (j - i) / 2;
            if (nums[mid] < target) {
                i = mid + 1;
            } else if (nums[mid] > target) {
                j = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

public void moveZeroes(int[] nums) {
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        while (j < nums.length) {
            nums[j++] = 0;
        }
    }

public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int index = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[index]) {
                nums[++index] = nums[i];
            }
        }
        return index + 1;
    }

public int lastRemaining(int n, int m) {
        List<Integer> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int idx = 0;
        while (n > 1) {
            idx = (idx + m - 1) % n;
            list.remove(idx);
            n--;
        }
        return list.get(0);
    }

public int[] exchange(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i < j) {
            while (i < j && nums[i] % 2 == 1) {
                i++;
            }
            while (i < j && nums[j] % 2 == 0) {
                j--;
            }
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        return nums;
    }

public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return res;
    }

// quickSort 方法是快速排序的入口。它接受一个整数数组 nums、一个起始索引 low 和一个结束索引 high。
    // 如果 low 小于 high，则选择一个基准元素（通常选择最后一个元素），
    // 将数组划分为两部分，使得左边的元素都小于基准元素，右边的元素都大于基准元素。然后递归地对左右两部分进行快速排序。
    public void quickSort(int[] nums, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(nums, low, high);
            quickSort(nums, low, pivotIndex - 1);
            quickSort(nums, pivotIndex + 1, high);
        }
    }

    // partition 方法用于划分数组。它选择基准元素 pivot，并使用两个指针 i 和 j 遍历数组。
    // 如果 nums[j] 小于 pivot，则将 nums[j] 与 nums[i] 交换，
    // 并将 i 向后移动一位。最后，将基准元素 pivot 与 nums[i+1] 交换，
    // 使得基准元素位于正确的位置，并返回基准元素的索引。
    private int partition(int[] nums, int low, int high) {
        int pivot = nums[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (nums[j] < pivot) {
                i++;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, high);
        return i + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

public int[][] merge(int[][] intervals) {
        if(intervals==null||intervals.length<=1){
            return intervals;
        }
        Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
        List<int[]> merged=new ArrayList<>();
        int[] currentInterval=intervals[0];

        for (int i = 1; i < intervals.length; i++) {
            if(intervals[i][0]<=currentInterval[1]){
                currentInterval[1]=Math.max(currentInterval[1],intervals[i][1]);
            }else{
                merged.add(currentInterval);
                currentInterval=intervals[i];
            }
        }
        merged.add(currentInterval);
        return merged.toArray(new int[merged.size()][]);
    }

public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        
        // 查找第一个位置
        int first = findFirst(nums, target);
        if (first == -1) {
            return result; // 未找到目标元素，返回初始结果
        }
        
        // 查找最后一个位置
        int last = findLast(nums, target);
        
        result[0] = first;
        result[1] = last;
        return result;
    }
    
    private int findFirst(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int first = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;         
            if (nums[mid] >= target) {
                right = mid - 1;
                if (nums[mid] == target) {
                    first = mid; // 更新第一个位置
                }
            } else {
                left = mid + 1;
            }
        }
        return first;
    }
    
    private int findLast(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int last = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;         
            if (nums[mid] <= target) {
                left = mid + 1;
                if (nums[mid] == target) {
                    last = mid; // 更新最后一个位置
                }
            } else {
                right = mid - 1;
            }
        }       
        return last;
    }

1. 从右到左遍历给定的排列，找到第一个破坏升序的相邻元素对，记为i-1和i。即找到满足nums[i-1] < nums[i]的i值。 
 
2. 如果找不到这样的相邻元素对，说明给定排列已经是字典序最大的排列，将其翻转为最小排列即可。 
 
3. 如果找到了相邻元素对，从右到左找到第一个大于nums[i-1]的元素，记为j。 
 
4. 交换nums[i-1]和nums[j]。 
 
5. 将从i开始到最右边的元素进行翻转，以得到下一个字典序更大的排列。
    
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        // 从右到左找到第一个破坏升序的相邻元素对
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
    
        if (i >= 0) {
            int j = nums.length - 1;
            // 从右到左找到第一个大于nums[i]的元素
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            // 交换nums[i]和nums[j]
            swap(nums, i, j);
        }
        // 翻转从i+1到最右边的元素
        reverse(nums, i + 1);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int[] nums, int start) {
        int i = start;
        int j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

public int maxProduct(int[] nums) {
        int maxProduct = nums[0];
        //currentMax 和 currentMin 来分别记录以当前元素结尾的子数组的最大乘积和最小乘积
        int currentMax = nums[0];
        int currentMin = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            //如果遇到负数，我们交换 currentMax 和 currentMin 的值，以保证在乘积计算中能够得到最大的乘积
            if (nums[i] < 0) {
                int temp = currentMax;
                currentMax = currentMin;
                currentMin = temp;
            }
            
            currentMax = Math.max(nums[i], currentMax * nums[i]);
            currentMin = Math.min(nums[i], currentMin * nums[i]);
            
            maxProduct = Math.max(maxProduct, currentMax);
        }
        
        return maxProduct;
    }

public int subarraySum(int[] nums, int k) {
        int count = 0;
        int sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); // 初始化前缀和为0的次数为1，用于处理数组中某个子数组的和正好等于k的情况
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            // 如果最新的前缀和-k的结果在map中，说明存在j-i这个连续区间和为k。
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }

public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0;
        int sum = 0;
        int count = Integer.MAX_VALUE;
        while (right < nums.length) {
            sum += nums[right];
            // 此处还得是while
            while (sum >= target) {
                count = Math.min(count, right - left + 1);
                sum -= nums[left];
                left++;
            }
            right++;
        }
        return count == Integer.MAX_VALUE ? 0 : count;
    }

public void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;
        
        while (mid <= high) {//必须用mid判断，方便mid=0时，置换到前面
            if (nums[mid] == 0) {
                swap(nums, low++, mid++);
            } else if (nums[mid] == 2) {
                swap(nums, mid, high--);
            } else { // nums[mid] == 1
                mid++;
            }
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

public static int rotatedBinarySearch(int[] array, int target){	
    if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int left = 0, right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止溢出
            
            // 找到目标值，直接返回
            if (nums[mid] == target) {
                return mid;
            }
            
            // 判断左半部分是否有序
            if (nums[left] <= nums[mid]) {
                // 目标值在左半部分
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1; // 在左半部分查找
                } else {
                    left = mid + 1; // 在右半部分查找
                }
            } 
            // 右半部分有序
            else {
                // 目标值在右半部分
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1; // 在右半部分查找
                } else {
                    right = mid - 1; // 在左半部分查找
                }
            }
        }
        
        return -1; // 没有找到目标值
    }
}

public String addStrings(String num1, String num2) {
       StringBuilder res = new StringBuilder();
        int m = num1.length() - 1, n = num2.length() - 1;
        int carry = 0;
        while (m >= 0 || n >= 0) {
            int n1 = m >= 0 ? num1.charAt(m) - '0' : 0;
            int n2 = n >= 0 ? num2.charAt(n) - '0' : 0;
            int ans = n1 + n2 + carry;
            carry = ans / 10;
            res.append(ans % 10);
            m--;
            n--;
        }
        if (carry == 1) {
            res.append(carry);
        }
        return res.reverse().toString(); 
    }

public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (String s : strs) {
            while (s.indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }
        return prefix;
    }

public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        int left = 0, right = 0;
        Set<Character> set = new HashSet<>();
        while (right < s.length()) {
            if (!set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                maxLength = Math.max(maxLength, right - left + 1);
                right++;
            } else {
                set.remove(s.charAt(left));
                left++;
            }
        }
        return maxLength;
    }

public String getLongestPalinedromeString(String s) {
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            String s1 = palinedrome(s, i, i);
            String s2 = palinedrome(s, i, i + 1);
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }
        return res;
    }

    /**
     * 中心往两边扩展寻找回文串
     */
    private String palinedrome(String s,int i,int j){
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
        }
        return s.substring(i+1,j);
        //i + 1：i 指针在最后一次循环中被减到了回文串开始位置的前一个字符，所以 i + 1 恰好指向了回文串的开始位置。j：j 指针在最后一次循环中被增到了回文串结束位置的下一个字符，所以 j 实际上超出了回文串的范围。但是 substring 方法的结束索引是不包含在内的，所以 j 恰好指明了回文串的结束位置。
    }

public String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        int[] res = new int[m + n];

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                // num1[i] 和 num2[j] 的乘积对应的就是 res[i+j] 和 res[i+j+1] 这两个位置.
                int p1 = i + j; // 进位
                int p2 = i + j + 1; //当前位

                int sum = mul + res[p2];
                res[p1] += sum / 10;
                res[p2] = sum % 10;
            }
        }

        StringBuilder str = new StringBuilder();
        for (int i = 0; i < res.length; i++) {
            if (i == 0 && res[i] == 0) {
                continue;
            }
            str.append(res[i]);
        }
        return str.toString();
    }

public int countSubstrings(String s) {
        int count = 0;
        
        for (int i = 0; i < s.length(); i++) {
            count += expandAroundCenter(s, i, i); // 以单个字符为中心扩展
            count += expandAroundCenter(s, i, i + 1); // 以两个字符之间为中心扩展
        }
        
        return count;
    }
    
    private int expandAroundCenter(String s, int left, int right) {
        int count = 0;
        
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
        
        return count;
    }

public boolean isValid(String s) {
        //如果为奇数，肯定无效
        if(s.length()%2==1){
            return false;
        }

        Map<Character,Character> map=new HashMap<>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');

        Deque<Character> stack=new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c=s.charAt(i);
            if(map.containsKey(c)){
                if(stack.isEmpty()||stack.peek()!=map.get(c)){
                    return false;
                }
                stack.pop();
            }else{
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }

class MyQueue {
        Stack<Integer> stack1;
        Stack<Integer> stack2;

        public MyQueue() {
            stack1 = new Stack<>();
            stack2 = new Stack<>();
        }

        public void push(int x) {
            stack1.push(x);
        }

        public int pop() {
            if (stack2.isEmpty()) {
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }

        public int peek() {
            if(stack2.isEmpty()){
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            }
            return stack2.peek();
        }

        public boolean empty() {
            return stack1.isEmpty() && stack2.isEmpty();
        }
    }

class MinStack {
        Stack<Integer> stack1;
        Stack<Integer> stack2;
        public MinStack() {
            stack1=new Stack<>();
            stack2=new Stack<>();
        }

        public void push(int val) {
            stack1.push(val);
            if (stack2.isEmpty() || stack2.peek() >= val) {
                stack2.push(val);
            }
        }

        public void pop() {
            if(stack2.peek().equals(stack1.pop())){ //此处同时进行了stack1的pop操作
                stack2.pop();
            }
        }

        public int top() {
            return stack1.peek();
        }

        public int getMin() {
            return stack2.peek();
        }
    }

public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack=new Stack<>();
        int i=0;
        for(int c:pushed){
            stack.push(c);
            while(!stack.isEmpty()&&stack.peek()==popped[i]){
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }

public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<String> strStack = new Stack<>();
        StringBuilder res = new StringBuilder();

        int index = 0;
        while (index < s.length()) {
            char c = s.charAt(index);
            if (Character.isDigit(c)) {
                int count = 0;
                // 此处获取字符前的重复数，可能>10
                while (Character.isDigit(s.charAt(index))) {
                    count = count * 10 + (s.charAt(index) - '0');
                    index++;
                }
                countStack.push(count);
            } else if (c == '[') {
                // 如果遇到左括号 [ ，则将当前解码的字符串压入 stringStack ，并重置 result 为一个新的空字符串
                strStack.push(res.toString());
                res.setLength(0);
                index++;
            } else if (c == ']') {
                // 如果遇到右括号 ] ，则从 stringStack 中弹出一个字符串，并根据重复次数将 result 追加到弹出的字符串中
                StringBuilder temp = new StringBuilder(strStack.pop());
                // 此处由于定义的Stack<String>，因此直接弹出一次得到字符串。
                int repeatTimes = countStack.pop();
                for (int i = 0; i < repeatTimes; i++) {
                    temp.append(res);
                }
                res = temp;
                index++;
            } else {
                // 如果遇到其他字符，则直接将其追加到 result 中。 
                res.append(c);
                index++;
            }
        }
        return res.toString();
    }

public int[] dailyTemperatures(int[] T) {
    int[] result = new int[T.length];
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < T.length; i++) {
        while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
            int index = stack.pop();
            result[index] = i - index;
        }
        stack.push(i);
    }

    return result;
}

public int trap(int[] height){
        if(height==null){
            return 0;
        }
        Stack<Integer> stack=new Stack<>();
        int ans=0;
        for(int i=0;i<height.length;i++){
            //当栈不空，判断当前指向height[i]是否大于上一个已入栈元素的高
            while(!stack.isEmpty()&&height[stack.peek()]<height[i]){
                int curIdx=stack.pop();
                //如果栈顶元素一直相等，那么一直pop出去，只留下第一个。
                while(!stack.isEmpty()&&height[stack.peek()]==height[curIdx]){
                    stack.pop();
                }
                if(!stack.isEmpty()){
                    int stackTop=stack.peek();
                    // stackTop此时指向的是此次接住的雨水的左边界的位置。右边界是当前的柱体，即i。
                    // Math.min(height[stackTop], height[i]) 是左右柱子高度的min，减去height[curIdx]就是雨水的高度。
                    // i - stackTop - 1 是雨水的宽度。
                    ans += (Math.min(height[stackTop], height[i]) - height[curIdx]) * (i - stackTop - 1);

                }
            }
            stack.add(i);//单调栈添加元素在此
        }
        return ans;
    }

public ListNode reverseList(ListNode head) {
        ListNode pre=null;
        ListNode cur=head;
        while (cur!=null){
            ListNode temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode mergeList = new ListNode(-1);
        ListNode cur=mergeList;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }

        cur.next = list1 != null ? list1 : list2;
        return mergeList.next;
    }

public boolean hasCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode first = headA, second = headB;
        while (first != second) {
            first = first != null ? first.next : headB;
            second = second != null ? second.next : headA;
        }
        return first;
    }

public ListNode kthReverseNode(ListNode head, int k) {
        ListNode fast = head, slow = head;
        while (k-- != 0) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        ListNode fast = head, slow = head;
        ListNode cur = head, pre = null;
        while (fast != null && fast.next != null) { //快慢指针寻找中点并反转前半部分
            cur = slow;
            fast = fast.next.next;
            slow = slow.next;
            cur.next = pre;
            pre = cur;
        }
        if (fast != null) {
            slow = slow.next; //slow指向后半部分
        }

        while (slow != null && pre != null) { // 比较
            if (slow.val != pre.val) {
                return false;
            }
            slow = slow.next;
            pre = pre.next;
        }
        return true;
    }

public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy=new ListNode(-1);
        dummy.next=head;
        ListNode pre=dummy;

        for(int i=1;i<left;i++){
            pre=pre.next;
        }

        // 在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。
        // //pre-cur-node-node.next
        ListNode cur=pre.next;
        for(int i=left;i<right;i++){
            ListNode node=cur.next;
            cur.next=node.next;
            node.next=pre.next;
            pre.next=node;
        }
        return dummy.next;
    }

public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast=fast.next.next;
            slow=slow.next;

            if (fast == slow) {
                ListNode index1 = fast;
                ListNode index2 = head;
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }

/**
     * 10、重排链表
     * 【思路】：1、找到中间结点，反转后半部分链表，然后交替合并。
     */
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        // 1、获得中间结点
        ListNode mid = findMid(head);
        ListNode head2=mid.next;
        // 2、获得前半部分链表
        mid.next=null;
        // 3、反转后半部分链表
        head2=reverse(head2);
        // 4、合并
        ListNode head1=head;
        mergeLists(head1,head2);
    }

    private void mergeLists(ListNode head1, ListNode head2) {
        while (head1 != null && head2 != null) {
            ListNode temp1 = head1.next;
            ListNode temp2 = head2.next;

            // 此处需要改变head1.next的值，因此需要上面的暂存操作。
            head1.next = head2;
            head1 = temp1;

            head2.next = head1;
            head2 = temp2;
        }
    }

    private ListNode findMid(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    private ListNode reverse(ListNode head){
        ListNode pre=null;
        ListNode cur=head;
        while (cur!=null){
            ListNode temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }

public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 快慢指针找到链表中点，将链表拆分为两个子链表
        ListNode slow = head;
        ListNode fast = head;
        ListNode pre = null;
        while (fast != null && fast.next != null) {
            pre = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        //将链表从中点处分割成两个独立的链表。
        pre.next = null;

        // 递归对两个子链表进行排序
        ListNode left = sortList(head);
        ListNode right = sortList(slow);

        // 合并两个有序链表
        return merge(left, right);
    }

    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        cur.next = left == null ? right : left;
        return dummy.next;
    }

public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode tail = head;
        for (int i = 0; i < k; i++) {
            if (tail == null) { //注意用tail判空，不能用tail.next，存在NPC。
                return head;
            }
            tail = tail.next;
        }

        ListNode newHead = reverse(head, tail);
        head.next = reverseKGroup(tail, k);
        return newHead;

    }

    private ListNode reverse(ListNode head, ListNode tail) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != tail) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 分别定义奇偶结点
        ListNode odd = head;
        ListNode even = head.next;
 
        // 暂存偶结点头部
        ListNode temp = even;
    
        // 循环，even更快到尾部
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
 
            even.next = odd.next;
            even = even.next;
        }
        // 将所有奇结点的末尾接上偶结点的头
        odd.next = temp;
        return head;
    }

public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        // 计算链表长度并将尾节点与头节点相连
        int length = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            length++;
        }
        tail.next = head;

        // 计算实际需要右移的步数
        int steps = length - k % length;

        // 找到新的头节点和尾节点
        ListNode newTail = tail;
        while (steps > 0) {
            newTail = newTail.next;
            head = head.next;
            steps--;
        }
        newTail.next = null;

        return head;
    }

public ListNode partition(ListNode head, int x) {
        ListNode smallerHead = new ListNode(0);
        ListNode greaterHead = new ListNode(0);
        ListNode smaller = smallerHead;
        ListNode greater = greaterHead;

        while (head != null) {
            if (head.val < x) {
                smaller.next = head;
                smaller = smaller.next;
            } else {
                greater.next = head;
                greater = greater.next;
            }
            head = head.next;
        }

        greater.next = null;
        smaller.next = greaterHead.next;

        return smallerHead.next;
    }

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        int carry = 0;
        while (l1 != null || l2 != null) {
            int val1 = l1 == null ? 0 : l1.val;
            int val2 = l2 == null ? 0 : l2.val;

            int sum = val1 + val2 + carry;
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;

            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry == 1) {
            cur.next = new ListNode(1);
        }
        return dummy.next;
    }

public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }

        ListNode temp=head.next;
        head.next=swapPairs(temp.next);
        temp.next=head;
        return temp;
    }

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;

        // 将快指针向前移动n步
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        // 快慢指针一起向前移动，直到快指针到达链表末尾
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 删除倒数第k个节点
        slow.next = slow.next.next;

        return dummy.next;
    }

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        inOrder(root,res);
        return res;
    }
    private void inOrder(TreeNode root, List<Integer> res) {
        if(root==null){
            return;
        }
        inOrder(root.left,res);
        res.add(root.val);
        inOrder(root.right,res);
    }

public List<Integer> inorderTraversalByIterator(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        Deque<TreeNode> stack=new LinkedList<>();
        while (root!=null||!stack.isEmpty()){
            while (root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            res.add(root.val);
            root=root.right;
        }
        return res;
    }

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }

public List<Integer> preOrderTraversalByIterator(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        if(root==null){
            return res;
        }

        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            // 入栈，根右左，那么出栈就是根左右（前序）
            TreeNode node=stack.pop();
            res.add(node.val);
            while (node.right!=null){
                stack.push(node.right);
            }
            while (node.left!=null){
                stack.push(node.left);
            }
        }
        return res;
    }

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);             
    }

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            //入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果。
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }

public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);

                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            result.add(currentLevel);
        }

        return result;
    }

public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left=maxDepth(root.left);
        int right=maxDepth(root.right);
        return Math.max(left,right)+1;
    }

public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }

public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return symmetric(root.left, root.right);
    }

    private boolean symmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null || left.val != right.val) {
            return false;
        }
        return symmetric(left.left, right.right) && symmetric(left.right, right.left);
    }