This is the multi-page printable view of this section. Click here to print.
链表
- 1: 138. 随机链表的复制
- 2: 141. 环形链表
- 3: 160. 相交链表
- 4: 19. 删除链表的倒数第 N 个结点
- 5: 206. 反转链表
- 6: 21. 合并两个有序链表
- 7: 23. 合并 K 个升序链表
- 8: 24. 两两交换链表中的节点
- 9: 25. K 个一组翻转链表
1 - 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 作为传入参数。
难度:
中等
分析:
和通常的深拷贝不同的是, 这里的节点多了随机指针
那么在拷贝随机指针之前, 就必须有原链表
因此分为三步
- 拷贝原链表
- 拷贝随机指针
- 分离链表
复制节点并插入原节点后面：
while (cur != null) {
Node newNode = new Node(cur.val);
newNode.next = cur.next;
cur.next = newNode;
cur = newNode.next;
}
比如原链表：A->B->C 变成 A->A’->B->B’->C->C'
复制随机指针：
while (cur != null) {
if (cur.random != null) {
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
利用第一步创建的节点关系，设置复制节点的random指针：
- 如果原节点A的random指向节点C
- 那么A’的random就应该指向C’（即C的next）
分离两个链表：
while (cur != null) {
Node next = cur.next.next;
Node copy = cur.next;
copyCur.next = copy;
copyCur = copy;
cur.next = next;
cur = next;
}
将交织在一起的链表分开：
- 原链表恢复原样：A->B->C
- 得到复制的链表：A’->B’->C'
整体:
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;
}
}
2 - 141. 环形链表
题意:
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
难度:
简单
示例:
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
解析:
使用循环遍历链表查重的方法内存和时间开销很大
这里介绍一种算法, 龟兔赛跑算法, 就是快慢指针
定义两个指针, 二者遍历速度不同, 这样就可以保证快指针在有环的情况下可以追上慢指针
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;
}
}
3 - 160. 相交链表
题意:
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交
题目数据 保证 整个链式结构中不存在环。
难度:
简单
示例:
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
分析:
判断相交在链表中是一项很基本, 也很重要的算法
我们可以将两个链表分别遍历并放入哈希表中去重, 但是当数组较长时会浪费许多资源
其实这道题的核心是找出第一个相交节点, 而非全部节点, 所以可以使用双指针同时遍历两个链表
大致思路如下:
- 设置两个指针分别指向两个链表的头部
- 判断是否重复, 重复即为相交
- 首先移动其中一个指针, 判断重复
- 移动另一个指针, 判断重复
- 直至某个指针为空返回false
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;
4 - 19. 删除链表的倒数第 N 个结点
题意:
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例:
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
难度:
中等
分析:
题目一共要求做两件事
- 找到链表的倒数第n个节点
- 删除该节点
对于单项链表, 如何找到节点的位置?
可以两次遍历, 第一次遍历拿链表长度
第二次才获取具体的节点
如何删除该节点?
删除节点涉及到三个部分
前驱节点, 该节点, 后驱节点
所以我们在第一步拿到前驱节点, 并保存后驱节点, 修改引用就算删除完毕
遍历链表
while (current != null) { length++; current = current.next; }
注意是倒数第 n 个节点，所以要用链表的长度减去 n。倒数第 4 个节点的前一个节点就是 5-4=1，也就是第一个节点。
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;
}
}
5 - 206. 反转链表
题意:
翻转给定的链表
示例:
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
难度:
简单
分析:
链表翻转有两种方法
- 迭代
- 递归
这里我们用迭代法
从图中可以看出, 对链表的翻转可以理解为箭头方向变化
这样我们可以讲链表转为两两一组的节点对, 从头开始迭代
对于节点对, 我们分为首节点和次节点, 在单向链表, 次节点指向其他节点, 一旦断开次节点的引用, 其他节点会丢失
所以需要提前存储其他节点
改变引用关系大致流程如下:
- 获得首节点
- 临时存储其他节点
- 次节点指向首节点
- 迭代, 次节点为下一代的首节点, 临时存储节点为次节点
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;
}
}
6 - 21. 合并两个有序链表
题意:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
难度:
简单
示例:
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
分析:
提供的链表有序, 所以可以同时遍历. 连接较小的节点即可
- 创建哑结点, 作为链表头, 当前节点为哑结点
- 同时比较两个链表, 当前节点连接较小节点, 当前节点后驱, 当前节点为新节点
- 直至某个链表遍历完成, 拼接其剩余节点
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;
}
}
7 - 23. 合并 K 个升序链表
题意:
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例:
合并链表. 最容易想到的就是依次合并
首先合并 1,2 之后合并3 这样依次合并
如何合并?
因为所提供的链表都是有顺序的 所以采用双指针方式
- 比较两个节点的值
- 将较小的节点连接到结果链表
- 移动较小节点所在链表的指针
- 移动结果链表的指针
- 遍历完成后, 剩余节点直接拼接
但很遗憾，这样做的话，每一次合并后的新链表就会非常臃肿，并且在与第 K 个链表合并时，之前链表的节点会多次被访问。
我们可以使用分治的思想解决
为了解决臃肿和重复遍历的问题, 把链表的整体合并转为两两合并链表的子问题
首先判空
if (lists == null || lists.length == 0) {
return null;
}
设置间隔, 每次只对间隔的头结点做合并操作
int interval = 1; // 初始间隔为1
while (interval < n) { // 当间隔小于链表总数时继续循环
这里使用interval来控制合并的步长，比如：
- 第一轮：interval = 1，两两合并
- 第二轮：interval = 2，每次合并相隔2个位置的链表
- 第三轮：interval = 4，每次合并相隔4个位置的链表
合并
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;
}
}
8 - 24. 两两交换链表中的节点
题意:
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。 你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
难度:
中等
示例:
输入：head = [1,2,3,4] 输出：[2,1,4,3]
分析:
看到这道题，我们要先搞清楚什么是两两交换，比如 1->2->3->4，交换后就是 2->1->4->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 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;
}
}
9 - 25. K 个一组翻转链表
/**
* 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;
}
}