文章目录
- 138.【中等】随机链表的复制
- 92.【中等】反转链表 II
- 25.【困难】K 个一组翻转链表
- 19.【中等】删除链表的倒数第 N 个结点
- 82.【中等】删除排序链表中的重复元素 II
🌈你好呀！我是 山顶风景独好
💕欢迎来到我的博客，很高兴能够在这里和您见面！
💕希望您在这里可以感受到一份轻松愉快的氛围！
💕这里不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。
🚀 欢迎一起踏上探险之旅，挖掘无限可能，共同成长！
138.【中等】随机链表的复制
题目描述
- 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
- 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
- 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
- 返回复制链表的头节点。
- 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
- val：一个表示 Node.val 的整数。
- random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
- 你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1：
- 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
- 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
- 输入：head = [[1,1],[2,1]]
- 输出：[[1,1],[2,1]]
示例 3：
- 输入：head = [[3,null],[3,0],[3,null]]
- 输出：[[3,null],[3,0],[3,null]]
/*
// Definition for a 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) { // 如果原链表为空，则直接返回null if(head == null) return null; // 定义一个指针cur，用于遍历原链表 Node cur = head; // 1. 复制各节点，并构建拼接链表 // 遍历原链表，在每个节点后面复制一个新的节点，并链接到原节点的next while(cur != null) { // 创建一个新节点tmp，其值与当前节点cur相同 Node tmp = new Node(cur.val); // 将新节点tmp的next指向当前节点cur的下一个节点 tmp.next = cur.next; // 将当前节点cur的next指向新节点tmp，实现新旧节点的拼接 cur.next = tmp; // 移动cur到下一个节点 cur = tmp.next; } // 2. 构建各新节点的 random 指向 // 再次遍历原链表（实际上是新旧节点拼接的链表），设置新节点的random指针 cur = head; while(cur != null) { // 如果当前节点cur的random指针不为空 if(cur.random != null) // 将当前节点cur的下一个节点（即新节点）的random指向原节点cur的random指针的下一个节点（即对应的新节点） cur.next.random = cur.random.next; // 移动cur到下一个新旧节点对 cur = cur.next.next; } // 3. 拆分两链表 // 将新旧节点拼接的链表拆分为两个独立的链表：原链表和新链表 cur = head.next; // cur指向新链表的头节点 Node pre = head, res = head.next; // pre用于遍历原链表，res用于保存新链表的头节点 // 遍历链表，拆分新旧节点 while(cur.next != null) { // 将原链表的当前节点pre的next指向下一个新节点 pre.next = pre.next.next; // 将新链表的当前节点cur的next指向下一个新节点 cur.next = cur.next.next; // 移动pre和cur到下一个节点 pre = pre.next; cur = cur.next; } // 单独处理原链表的尾节点，将其next置为null pre.next = null; // 返回新链表的头节点 return res; }
}
92.【中等】反转链表 II
题目描述
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
- 输入：head = [1,2,3,4,5], left = 2, right = 4
- 输出：[1,4,3,2,5]
示例 2：
- 输入：head = [5], left = 1, right = 1
- 输出：[5]
class Solution { // 反转从位置 left 到 right 的链表部分 public ListNode reverseBetween(ListNode head, int left, int right) { // 创建一个哑节点dummy，它的next指向head，这样可以避免处理头节点为null或left为1的特殊情况 ListNode dummy = new ListNode(0, head); // p0指针用于找到需要反转部分的起始位置的前一个节点 ListNode p0 = dummy; // 移动p0指针到left位置的前一个节点 for (int i = 0; i < left - 1; ++i) p0 = p0.next; // pre指针用于反转过程中的前一个节点 ListNode pre = null; // cur指针指向当前需要处理的节点 ListNode cur = p0.next; // 反转从left到right的链表部分 for (int i = 0; i < right - left + 1; ++i) { // nxt指针暂存cur的下一个节点，因为下一步cur.next会被修改 ListNode nxt = cur.next; // 将cur的next指针指向前一个节点，实现反转 cur.next = pre; // pre指针向后移动 pre = cur; // cur指针向后移动 cur = nxt; } // 将p0的next指针指向反转后的部分的最后一个节点（即原来的right位置的节点） // 这一步很重要，因为它连接了反转部分和原链表的其他部分 p0.next.next = cur; // 将p0的next指针指向反转后的部分的头节点（即原来的left位置的节点） // 这一步将反转部分与原链表的其他部分连接起来 p0.next = pre; // dummy.next是反转后整个链表的头节点，所以返回它 return dummy.next; }
}
25.【困难】K 个一组翻转链表
题目描述
- 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
- k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
- 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
- 输入：head = [1,2,3,4,5], k = 2
- 输出：[2,1,4,3,5]
示例 2：
- 输入：head = [1,2,3,4,5], k = 3
- 输出：[3,2,1,4,5]
class Solution { // 反转链表中每k个节点 public ListNode reverseKGroup(ListNode head, int k) { // 创建一个哑节点（hair node），方便处理头节点反转的情况 ListNode hair = new ListNode(0); hair.next = head; // pre指针用于指向当前需要反转的k个节点的前一个节点 ListNode pre = hair; // 当头节点不为空时，循环进行反转 while (head != null) { // tail指针用于指向当前需要反转的k个节点的最后一个节点 ListNode tail = pre; // 查看剩余部分长度是否大于等于 k // 如果剩余长度小于k，则无需再反转，直接返回结果 for (int i = 0; i < k; ++i) { tail = tail.next; if (tail == null) { // 如果tail为null，说明剩余节点不足k个，直接返回结果 return hair.next; } } // nex指针用于保存tail的下一个节点，即下一个需要反转的k个节点的头节点 ListNode nex = tail.next; // 调用myReverse方法反转当前k个节点，并返回反转后的头尾节点 ListNode[] reverse = myReverse(head, tail); // 更新head为反转后的头节点 head = reverse[0]; // 更新tail为反转后的尾节点 tail = reverse[1]; // 把子链表重新接回原链表 // pre.next指向反转后的头节点 pre.next = head; // tail.next指向下一个需要反转的k个节点的头节点 tail.next = nex; // pre指针移动到当前反转的k个节点的尾节点 pre = tail; // head指针移动到下一个需要反转的k个节点的头节点 head = tail.next; } // 返回反转后的链表头节点 return hair.next; } // 反转链表中的节点，从head到tail（不包括tail） public ListNode[] myReverse(ListNode head, ListNode tail) { // prev指针用于指向反转后的前一个节点，初始为tail的下一个节点 ListNode prev = tail.next; ListNode p = head; while (prev != tail) { // nex指针用于保存p的下一个节点 ListNode nex = p.next; // 反转p的指向 p.next = prev; // prev向后移动 prev = p; // p向前移动 p = nex; } // 返回反转后的头尾节点数组 return new ListNode[]{tail, head}; }
}
19.【中等】删除链表的倒数第 N 个结点
题目描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
- 输入：head = [1,2,3,4,5], n = 2
- 输出：[1,2,3,5]
示例 2：- 输入：head = [1], n = 1
- 输出：[]
示例 3：- 输入：head = [1,2], n = 1
- 输出：[1]
/*** 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 { // 定义一个方法，用于从链表的末尾删除第n个节点 public ListNode removeNthFromEnd(ListNode head, int n) { // 创建一个虚拟头节点dummy，其值为0，并指向原链表的头节点head // 这样做的目的是为了方便处理删除头节点的情况 ListNode dummy = new ListNode(0, head); // 定义两个指针first和second，都初始化为链表的头节点 // first指针用于先走n步，以确定与second指针之间的间隔 ListNode first = head; ListNode second = dummy; // first指针先走n步 for (int i = 0; i < n; ++i) { first = first.next; } // 当first指针到达链表末尾时，second指针指向的下一个节点即为要删除的节点的前一个节点 // 通过移动first和second指针，保持它们之间的间隔始终为n while (first != null) { first = first.next; second = second.next; } // 删除second指针指向的下一个节点（即要删除的节点） // 通过将second.next指向second.next.next来实现 second.next = second.next.next; // 返回新的链表的头节点（由于我们使用了dummy，所以实际返回的是dummy.next） ListNode ans = dummy.next; return ans; }
}
82.【中等】删除排序链表中的重复元素 II
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
- 输入：head = [1,2,3,3,4,4,5]
- 输出：[1,2,5]
示例 2：
- 输入：head = [1,1,1,2,3]
- 输出：[2,3]
/*** 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 deleteDuplicates(ListNode head) { // 如果链表为空，则直接返回 if (head == null) { return head; } // 创建一个虚拟头节点dummy，其值为0，并指向原链表的头节点head // 这样做是为了方便处理删除头节点的情况 ListNode dummy = new ListNode(0, head); // cur指针初始化为虚拟头节点dummy，用于遍历链表 ListNode cur = dummy; // 当cur的下一个节点和再下一个节点都不为空时，进行循环 while (cur.next != null && cur.next.next != null) { // 如果cur的下一个节点和再下一个节点的值相等，说明有重复元素 if (cur.next.val == cur.next.next.val) { // 记录当前重复元素的值 int x = cur.next.val; // 删除所有值为x的节点，直到cur的下一个节点的值不再等于x while (cur.next != null && cur.next.val == x) { cur.next = cur.next.next; // 删除当前重复节点 } } else { // 如果没有重复元素，cur指针向后移动一位 cur = cur.next; } } // 遍历结束后，返回处理后的链表的头节点（虚拟头节点的下一个节点） return dummy.next; }
}
✨ 这就是今天要分享给大家的全部内容了，我们下期再见！😊
🏠 我在CSDN等你哦！我的主页😍
