class Solution {

    public int maxArea(int[] height) {

        //初始化指针

        int left = 0;

        int right = height.length - 1;

        //面积

        int maxSize = 0;

        while(left < right){

           maxSize =  Math.max(maxSize, Math.min(height[left], height[right]) * (right - left));

            // 移动指针

            if (height[left] <= height[right]) {

                left++;  // 增大左边的指针

            } else {

                right--; // 减小右边的指针

            }

        }

        return maxSize;

    }

}

 for(int add = 0; add < length; add++){
            for(int pair = add + 1; pair < length; pair++ ){
                if(nums[add] +nums[pair] == target){
                    int[] result = new int[]{add, pair};
                    return result;
                }
            }
}

class Solution {

    public int[] twoSum(int[] nums, int target) {

       //但是遍历数组的方法太麻烦, 我们换用查找复杂度为 O1 的哈希

       //哈希表存储当前索引和预期值

       HashMap<Integer, Integer> map = new HashMap<>();

       int length = nums.length;

       for(int value = 0; value < length; value++){

        //补数, 我们根据补数来查找索引

        int completement = target - nums[value];

        //先查找是否存在, 存在就直接返回

         //匹配

         if(map.containsKey(completement)){

            int[] result = new int[]{value, map.get(completement)};

            return result;

         }

        //不存在, 放入map里面

        map.put(nums[value], value);

    }

       return null;

    }

}

import java.util.*;

  

public class Solution {

    public List<List<String>> groupAnagrams(String[] strs) {

        // 哈希表存储排序后的字符串作为键，异位词作为值

        Map<String, List<String>> map = new HashMap<>();

        for (String s : strs) {

            // 将字符串转换为字符数组并排序

            char[] chars = s.toCharArray();

            Arrays.sort(chars);

            // 排序后的字符数组作为键

            String sortedStr = new String(chars);

            // 如果该键不存在，初始化一个新的列表

            map.putIfAbsent(sortedStr, new ArrayList<>());

            // 将原始字符串加入到对应的列表中

            map.get(sortedStr).add(s);

        }

        // 返回所有的异位词组

        return new ArrayList<>(map.values());

    }

}

public boolean isMirror(TreeNode r1, TreeNode r2){
	//第一出口, 左右节点同时为NULL
	if(r1 == null && r2 == null){
          return true;
    }
    
    //如果两个节点不同时为空, 代表左右两颗树层数不一致
    if(r1 == null || r2 == null){
            return false;
    }
    
    //递归体, 检查该层节点以及子树是否相等
    return (r1.val == r2.val) &&
        ismirror(r1.left, r2.right) &&
        ismirror(r2.left, r1.right);
}

 public int search(TreeNode root){

        //递归
		//归条件
        if(root == null){

            return 0;

        }
		//递右节点
        int left = search(root.left);
		//递右节点
        int right = search(root.right);
		//归条件
        return (right >= left) ? right + 1 : left + 1;

        }

class Solution {
    public int[][] generateMatrix(int n) {
        // 正确初始化二维数组
        int[][] matrix = new int[n][n];
        
        // 定义四个边界
        int left = 0;
        int right = n - 1;
        int top = 0;
        int bottom = n - 1;
        
        // 数字从1开始填充
        int num = 1;
        
        while (num <= n * n) {
            // 从左到右填充上边界
            for (int i = left; i <= right; i++) {
                matrix[top][i] = num++;
            }
            top++;
            
            // 从上到下填充右边界
            for (int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--;
            
            // 从右到左填充下边界
            for (int i = right; i >= left; i--) {
                matrix[bottom][i] = num++;
            }
            bottom--;
            
            // 从下到上填充左边界
            for (int i = bottom; i >= top; i--) {
                matrix[i][left] = num++;
            }
            left++;
        }
        
        return matrix;
    }
}

class Solution {

    public boolean canJump(int[] nums) {

        //最远位置, 最一开始是0

        int maxHeap = 0;

        //指向贪心节点的指针

        int pos = 0;

        //长度, 循环终止条件

        int length = nums.length;

        //极限情况

        if(length == 0 || length == 1){

            return true;

        }

        //迭代器

        for(; pos < length; ++pos){

            //拿节点

            int node = nums[pos];

            //判断节点是否可达

            if(maxHeap < pos){

                //该世代无法抵达

                return false;

            }

            //更新最远位置

            maxHeap = Math.max(maxHeap, nums[pos] + pos);

            //判断是否已经可以到达终点

            if(maxHeap >= length - 1){

                return true;

            }

        }

        //循环结束没有结果

        return false;

    }

}

while (cur != null) {
    Node newNode = new Node(cur.val);
    newNode.next = cur.next;
    cur.next = newNode;
    cur = newNode.next;
}

while (cur != null) {
    if (cur.random != null) {
        cur.next.random = cur.random.next;
    }
    cur = cur.next.next;
}

while (cur != null) {
    Node next = cur.next.next;
    Node copy = cur.next;
    copyCur.next = copy;
    copyCur = copy;
    cur.next = next;
    cur = next;
}

class Solution {

    public Node copyRandomList(Node head) {

        if (head == null) {

            return null;

        }

        // 第一步：在每个原节点后创建一个新节点

        Node cur = head;

        while (cur != null) {

            Node newNode = new Node(cur.val);

            newNode.next = cur.next;

            cur.next = newNode;

            cur = newNode.next;

        }

        // 第二步：处理random指针

        cur = head;

        while (cur != null) {

            if (cur.random != null) {

                cur.next.random = cur.random.next;

            }

            cur = cur.next.next;

        }

        // 第三步：分离两个链表

        Node dummy = new Node(0);

        Node copyCur = dummy;

        cur = head;

        while (cur != null) {

            // 保存下一个原始节点

            Node next = cur.next.next;

            // 复制的节点

            Node copy = cur.next;

            copyCur.next = copy;

            copyCur = copy;

            // 恢复原始链表

            cur.next = next;

            cur = next;

        }

        return dummy.next;

    }
}

public class Solution {

   public boolean hasCycle(ListNode head) {

    if (head == null || head.next == null) {

        return false;

    }

    ListNode slow = head;

    ListNode fast = head.next;

    while (slow != fast) {

        if (fast == null || fast.next == null) {

            return false;

        }

        slow = slow.next;

        fast = fast.next.next;

    }

    return true;

    }

}

public class Solution {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 定义两个指针，初始分别指向两个链表头部
  // 如果任一链表为空，则不可能相交

        if (headA == null || headB == null) {
            return null;
        }

        ListNode ptrA = headA;
        ListNode ptrB = headB;

        // 当两个指针不相等时继续遍历

        while (ptrA != ptrB) {
            // 移动指针A
            ptrA = ptrA == null ? headB : ptrA.next;
            // 移动指针B
            ptrB = ptrB == null ? headA : ptrB.next;
        }
         // 返回相交节点，如果不存在则返回null

        return ptrA;

 while (current != null) { length++; current = current.next; }

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建一个虚拟头节点，简化边界条件处理
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // 第一次遍历，计算链表的总长度
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }
        
        // 设置长度为到达要删除的节点的前一个节点
        int index = length - n;
        current = dummy;
        // 第二次遍历，找到要删除的节点的前一个节点
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        
        // 删除节点，即跳过要删除的节点
        current.next = current.next.next;
        
        return dummy.next;
    }
}

class Solution {

    public ListNode reverseList(ListNode head) {

        //迭代法

        ListNode current = head;

        ListNode previous = null;

        while(current != null){

            ListNode temp = current.next;

            current.next = previous;

            previous = current;

            current = temp;

        }

        return previous;

    }

}

class Solution {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        // 创建哑节点作为合并后链表的头部

        ListNode dummy = new ListNode(0);

        ListNode current = dummy;

        // 同时遍历两个链表，比较节点值

        while (l1 != null && l2 != null) {

            if (l1.val <= l2.val) {

                current.next = l1;

                l1 = l1.next;

            } else {

                current.next = l2;

                l2 = l2.next;

            }

            current = current.next;

        }

        // 将剩余节点接到合并后的链表末尾

        current.next = (l1 != null) ? l1 : l2;

        return dummy.next;

    }

}

if (lists == null || lists.length == 0) {
    return null;
}

int interval = 1;  // 初始间隔为1
while (interval < n) {  // 当间隔小于链表总数时继续循环

for (int i = 0; i < n - interval; i += interval * 2) {
    lists[i] = merge2Lists(lists[i], lists[i + interval]);
}

while (l1 != null && l2 != null) {
    if (l1.val <= l2.val) {
        current.next = l1;
        l1 = l1.next;
    } else {
        current.next = l2;
        l2 = l2.next;
    }
    current = current.next;
}

//处理剩余节点
current.next = (l1 != null) ? l1 : l2;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        int n = lists.length;
        int interval = 1;

        while (interval < n) {
            for (int i = 0; i < n - interval; i += interval * 2) {
                lists[i] = merge2Lists(lists[i], lists[i + interval]);
            }
            interval *= 2;
        }

        return lists[0];
    }

    private ListNode merge2Lists(ListNode l1, ListNode l2) {
        // 创建哑节点作为合并后链表的头部
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // 同时遍历两个链表，比较节点值
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        // 将剩余节点接到合并后的链表末尾
        current.next = (l1 != null) ? l1 : l2;

        return dummy.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        return swapAndConnect(head);
    }

    public ListNode swapAndConnect(ListNode node) {
        if (node == null || node.next == null) {
            // 如果当前节点或下一个节点为空，直接返回当前节点
            return node;
        }

        // 递归：获取后面的交换结果
        ListNode partner = node.next;
        ListNode next = swapAndConnect(partner.next);

        // 交换当前节点和下一个节点
        node.next = next;
        partner.next = node;

        // 返回交换后的新头节点
        return partner;
    }
}

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

     public ListNode reverseKGroup(ListNode head, int k) {

        // 基本判断

        if (head == null || k == 1) return head;

        // 计算当前组的长度是否够k个节点

        ListNode curr = head;

        int count = 0;

        while (curr != null && count < k) {

            curr = curr.next;

            count++;

        }

        // 如果不够k个节点，保持原有顺序

        if (count < k) return head;

        // 递归处理后续节点组

        curr = reverseKGroup(curr, k);

        // 翻转当前组的k个节点

        ListNode prev = curr;

        ListNode now = head;

        while (count > 0) {

            ListNode next = now.next;

            now.next = prev;

            prev = now;

            now = next;

            count--;

        }

        return prev;

    }

}