#leetcode
25.K个一组翻转链表
class Solution {
/**
* 以k个节点为一组反转链表
* @param head 链表头节点
* @param k 每组节点的数量
* @return 反转后的链表头节点
*/
public ListNode reverseKGroup(ListNode head, int k) {
// 创建一个虚拟头节点(dummy node)，简化边界条件处理
ListNode hair = new ListNode(0);
hair.next = head;
// pre指针始终指向当前待反转组的前一个节点
ListNode pre = hair;

while (head != null) {
// tail初始化为pre，用于寻找当前组的尾节点
ListNode tail = pre;

// 检查剩余节点数量是否足够k个
for (int i = 0; i < k; ++i) {
tail = tail.next;
// 如果不足k个，直接返回结果
if (tail == null) {
return hair.next;
}
}

// 记录下一组的头节点
ListNode nex = tail.next;

// 反转当前组的链表，返回反转后的头和尾
ListNode[] reverse = myReverse(head, tail);
head = reverse[0]; // 反转后的头节点
tail = reverse[1]; // 反转后的尾节点

// 把反转后的子链表重新接入原链表
pre.next = head; // 前驱节点连接反转后的头
tail.next = nex; // 反转后的尾连接下一组的头

// 更新pre和head指针，准备处理下一组
pre = tail;
head = tail.next;
}

return hair.next;
}

/**
* 反转从head到tail的子链表
* @param head 子链表头节点
* @param tail 子链表尾节点
* @return 反转后的头节点和尾节点数组
*/
public ListNode[] myReverse(ListNode head, ListNode tail) {
// prev初始化为tail.next ，这样第一次反转时头节点会指向下一组的头
ListNode prev = tail.next;
ListNode p = head;

// 反转链表的标准操作
while (prev != tail) {
ListNode nex = p.next; // 保存下一个节点
p.next = prev; // 反转当前节点的指针
prev = p; // prev指针前移
p = nex; // p指针前移
}

// 返回反转后的头节点(原tail)和尾节点(原head)
return new ListNode[]{tail, head};
}
}
138.复制带随机指针的链表
class Solution {
// 使用哈希表存储原始节点和复制节点的映射关系
// key: 原始链表中的节点
// value: 新链表中对应的复制节点
Map<Node, Node> cachedNode = new HashMap<Node, Node>();

/**
* 复制带有随机指针的链表（深度拷贝）
* @param head 原始链表的头节点
* @return 复制后的新链表头节点
*/
public Node copyRandomList(Node head) {
// 边界条件：如果原始链表为空，直接返回null
if (head == null) {
return null;
}

// 检查当前节点是否已经被复制过
// 如果哈希表中没有当前节点的记录，则需要进行复制
if (!cachedNode.containsKey(head)) {
// 创建新节点，复制原始节点的值
Node headNew = new Node(head.val);

// 将原始节点和新节点的映射关系存入哈希表
// 这一步必须在递归调用前完成，避免循环引用导致的无限递归
cachedNode.put(head, headNew);

// 递归复制next指针指向的节点
// 这里会深度复制整个链表结构
headNew.next = copyRandomList(head.next);

// 递归复制random指针指向的节点
// 由于使用了哈希表缓存，random指向的节点如果已经被复制会直接返回
headNew.random = copyRandomList(head.random);
}

// 返回当前节点对应的复制节点
// 如果节点已经复制过，直接从哈希表中获取
return cachedNode.get(head);
}
}

/*
// 链表节点的定义（供参考)
class Node {
int val;
Node next;
Node random;

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