刷题日记 - 8

/*
// Node类的定义，用于表示链表的节点
class Node {
    int val;      // 节点的值
    Node next;    // 指向下一个节点的指针
    Node random;  // 指向随机节点的指针

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        // 创建一个HashMap用于存储原节点和对应复制节点之间的映射关系
        HashMap<Node, Node> map = new HashMap<>();

        // 创建一个哑节点dummy，最终返回dummy.next作为新链表的头节点
        Node dummy = new Node(-1);
        Node t = dummy;  // t用于构建新链表
        Node p = head;   // p用于遍历原链表

        // 遍历原链表
        while (p != null) {
            Node randomNode = p.random;  // 获取当前节点的随机指针指向的节点
            Node tmp = null;
            Node tmpRandom = null;

            // 检查map中是否已存在当前节点的复制节点
            if (map.containsKey(p)) {
                tmp = map.get(p);  // 获取已存在的复制节点
            } else {
                tmp = new Node(p.val);  // 创建新的复制节点
                map.put(p, tmp);        // 存入map中
            }

            // 处理随机指针指向的节点
            if (randomNode != null) {
                if (map.containsKey(randomNode)) {
                    tmpRandom = map.get(randomNode);  // 获取已存在的复制节点
                } else {
                    tmpRandom = new Node(randomNode.val);  // 创建新的复制节点
                    map.put(randomNode, tmpRandom);        // 存入map中
                }
            }

            // 将复制节点连接到新链表上
            t.next = tmp;
            t = t.next;
            t.random = tmpRandom;  // 设置随机指针

            // 移动原链表指针
            p = p.next;
        }

        // 返回新链表的头节点
        return dummy.next;
    }
}

/**
 * 单链表节点的定义。
 * 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 reverseBetween(ListNode head, int left, int right) {
        // 如果left和right相同，无需反转，直接返回head
        if(left == right) return head;

        // 初始化指针p指向head，dummy节点指向head以便处理头节点的变化
        ListNode p = head;
        ListNode dummy = new ListNode(-1, head); // dummy节点指向链表头节点
        ListNode leftNode = dummy; // leftNode指向反转部分前的节点
        ListNode rightNode = null; // rightNode指向反转部分后的节点
        int count = 1;

        // 找到leftNode和rightNode
        while(count <= right + 1 && p != null) {
            if(count + 1 == left) leftNode = p; // 找到left的前一个节点
            if(count == right + 1) rightNode = p; // 找到right的下一个节点
            count++;
            p = p.next;
        }

        // 开始反转left到right区间的链表
        p = leftNode.next; // p指向需要反转的第一个节点
        ListNode q = p.next; // q指向需要反转的第二个节点
        ListNode t = q.next; // t指向需要反转的第三个节点

        // 反转链表的中间部分
        while(true) {
            q.next = p; // 当前节点q的next指向前一个节点p
            p = q; // p向前移动一位
            q = t; // q向前移动一位
            if(q == rightNode) break; // 如果q到达rightNode（反转结束），跳出循环
            t = q.next; // t向前移动一位
        }

        // 处理反转后的节点连接
        leftNode.next.next = rightNode; // 反转部分的最后一个节点指向rightNode
        leftNode.next = p; // leftNode的下一个节点指向反转后的第一个节点p

        // 返回新的链表头节点
        return dummy.next;
    }
}

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 如果k小于2，链表无需反转，直接返回原链表
        if(k < 2) return head;

        ListNode dummy = new ListNode(-1, head); // dummy节点指向链表头
        ListNode p = dummy; // 指针p初始化为dummy
        int count = 0; // 计数器，用于记录当前节点的位置
        ListNode pre = null; // 用于记录每组反转前的前一个节点

        while(true) {
            if(count == 0) {
                pre = p; // 当count为0时，pre指向当前p的位置
            }
            if(count == k + 1) { // 当count达到k+1时，说明当前组需要反转
                p = reverseBetween(pre, p); // 反转pre到p之间的节点
                count = 0; // 重置计数器
                continue;
            }
            count++; // 计数器增加
            if(p == null) break; // 如果p为空，说明链表遍历结束
            p = p.next; // p指向下一个节点
        }

        return dummy.next; // 返回新的链表头
    }

    // 反转pre和tail之间的节点（至少有两个节点）
    public ListNode reverseBetween(ListNode pre, ListNode tail) {
        ListNode p = pre.next; // p指向需要反转的第一个节点
        ListNode q = p.next; // q指向需要反转的第二个节点
        ListNode t = q.next; // t指向需要反转的第三个节点
        ListNode res = pre.next; // res最终指向反转部分的最后一个节点（反转前的第一个节点）

        while(true) {
            q.next = p; // 当前节点q的next指向前一个节点p
            p = q; // p向前移动一位
            q = t; // q向前移动一位
            if(q == tail) break; // 如果q到达tail，跳出循环
            t = q.next; // t向前移动一位
        }

        pre.next.next = tail; // 反转部分的最后一个节点连接到tail
        pre.next = p; // pre的next指向反转后的第一个节点p

        return res; // 返回反转前的第一个节点（现在是最后一个）
    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建一个dummy节点，指向head
        ListNode dummy = new ListNode(-1, head);
        // p和q指针都指向dummy
        ListNode p = dummy;
        ListNode q = dummy;
        int count = 0; // 计数器，用于记录p的移动次数

        // 遍历链表，p指针先走，q指针延迟n步
        while(p != null) {
            if(count > n) q = q.next; // 当p走了n步后，q开始移动
            p = p.next; // p指针向前移动
            count++; // 计数器增加
        }
        
        // q.next指向q.next.next，即跳过第n个节点
        q.next = q.next.next;
        
        // 返回新链表的头节点（dummy.next）
        return dummy.next;
    }
}

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // 如果链表为空或只有一个元素，直接返回链表
        if (head == null || head.next == null) return head;
        
        // 创建一个虚拟头节点，便于处理链表的边界情况
        ListNode dummy = new ListNode(-1);
        ListNode t = dummy; // t用于构建去重后的新链表
        ListNode p = head; // p用于遍历原始链表
        
        while (p != null) {
            ListNode q = p.next; // q用于指向p的下一个节点
            boolean flag = false; // flag标识当前元素是否为重复元素
            
            // 如果当前元素与下一个元素相同，继续移动p直到找到不同的元素
            while (q != null && q.val == p.val) {
                p = q;
                q = p == null ? null : p.next;
                flag = true; // 标记当前元素为重复元素
            }
            
            // 如果当前元素是重复的，跳过这个元素
            if (flag) {
                p = q;  //  ⭐后面不再做任何操作，因为不确定后面的元素是否是重复的
            } else {
                // 否则将当前元素加入到去重后的链表中
                t.next = p;
                t = t.next;
                p = q;
            }
        }
        
        t.next = null; // 确保去重后的链表尾部指向null
        return dummy.next; // 返回去重后的链表
    }
}

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null)return head;
        ListNode dummy = new ListNode(-1);
        ListNode t = dummy;
        ListNode p = head;
        while(p!=null){
            if(t==dummy||t.val!=p.val){
                t.next = p;
                t = t.next;
            }
            p = p.next;
        }
        t.next = null;
        return dummy.next;
    }
}

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        // 创建一个虚拟头节点，并将其指向head
        ListNode dummy = new ListNode(-1, head);
        
        // 如果k为0或者链表为空，直接返回链表
        if (k == 0 || head == null) return dummy.next;
        
        // 定义一个长度为501的数组来存储链表中的节点
        ListNode[] con = new ListNode[501];
        con[0] = dummy; // 将虚拟头节点放在数组的第一个位置
        
        ListNode p = head;
        int count = 1; // 记录链表节点数量
        
        // 遍历链表并将节点存储到数组中
        while (p != null) {
            con[count++] = p;
            p = p.next;
        }
        int total = count - 1; // 总节点数
        
        // 计算旋转后的实际移动步数
        k %= total;
        if (k != 0) {
            // 第一次反转整个链表
            reverseBetween(dummy, null);
            // 找到需要分割的位置
            ListNode tmp = con[total - k];
            // 第二次反转前半部分链表
            ListNode tmp_1 = reverseBetween(dummy, tmp);
            // 第三次反转后半部分链表
            reverseBetween(tmp_1, null);
        }
        return dummy.next; // 返回旋转后的链表头节点
    }

    // 反转链表从pre.next到tail的部分
    private ListNode reverseBetween(ListNode pre, ListNode tail) {
        ListNode res = pre.next; // 保存反转部分的开始节点
        ListNode p = pre.next;
        ListNode q = p.next;
        ListNode t = q == null ? null : q.next;
        
        // 进行反转操作
        while (q != tail) {
            q.next = p;
            p = q;
            q = t;
            t = q == null ? null : q.next;
        }
        pre.next.next = tail; // 将反转部分的尾节点指向tail
        pre.next = p; // 将pre.next指向反转后的头节点
        return res; // 返回反转部分的头节点
    }
}

class Solution {
    int count = -1; // 记录前序遍历数组中当前处理的节点位置
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 通过递归构建二叉树，初始时处理整个中序遍历数组
        return dfs(preorder, inorder, 0, inorder.length - 1);   
    }

    private TreeNode dfs(int[] preorder, int[] inorder, int left, int right) {
        // 如果当前范围无效（左边界大于右边界），返回null，表示该子树为空
        if (left > right) return null;
        
        // 前序遍历的下一个节点是当前子树的根节点
        TreeNode cur = new TreeNode(preorder[++count]);
        
        // 在中序遍历中找到当前根节点的位置
        int i = left;
        for (; i <= right; i++) {
            if (cur.val == inorder[i]) break;
        }
        
        // 递归构建左子树
        cur.left = dfs(preorder, inorder, left, i - 1);
        
        // 递归构建右子树
        cur.right = dfs(preorder, inorder, i + 1, right);
        
        // 返回构建好的当前根节点
        return cur;
    }
}

class Solution {
    int count;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        count = inorder.length;
        return dfs(inorder,postorder,0,count-1);
    }

    private TreeNode dfs(int[] inorder,int[] postorder,int left,int right){
        if(left>right)return null;
        int curVal = postorder[--count];
        TreeNode curNode = new TreeNode(curVal);

        int i = left;
        for(;i<=right;i++){
            if(inorder[i]==curVal)break;
        }

        curNode.right = dfs(inorder,postorder,i+1,right);
        curNode.left = dfs(inorder,postorder,left,i-1);
        return curNode;
    }
}