链表
分类:
- 单链表
- 双链表
特点:
- 链表对按索引(下标)查找不友好,时间复杂度O(n)
- 对插入友好,O(1)
遍历:
- 迭代:next 指针的存在使得链表可以使用 while 循环进行迭代
- 递归:链表的结构决定了它可以递归,比如打印当前链表:
public static void print(ListNode head) {
if (head == null) {
return;
}
System.out.println(head.val);
print(head.next); // 递归
}
技巧:
- 双指针技巧:一快一慢、一先一后
- 哨兵:设置一个伪节点作为 head 的 prev,或者作为 tail 的 next,以便在循环中一致地处理每一个节点
本节目前涵盖了 LeetCode 141,142,160,19,206,203,328,234,21,2,430,138,61 题,部分题目的解法还要参考 LeetCode 上的一些题解进行进一步的理解、优化;
环形链表-双指针技巧
1. 判定链表中是否存在环-141
双指针技巧
问题:如何判定链表中有环?
- 用哈希表,已经存在相同的 key,就表示出现了环
- 双指针技巧:如果出现了环,那么快的指针最终一定会与慢指针相遇;
双指针技巧实现:
- 慢指针每次走1步,快指针每次走2步,可知,假设存在环,那么在慢指针还没开始走第二圈的时候,快指针已经追上了慢指针(极端情况是链表首尾相连,此时,刚好在慢指针走完第一圈时,快指针走完了第二圈,相遇点=环的入口)
- 每次快指针多走一步,当快慢指针相遇时,快指针已经绕环走了 S 圈(S为环的长度)
public class Solution {
public boolean hasCycle(ListNode head) {
boolean res = false;
ListNode slow = head;
ListNode fast = head;
while (slow != null && fast != null) {
slow = slow.next;
fast = fast.next;
if (slow == null || fast == null) {
break;
}
fast = fast.next; // fast 多走一步
if (slow == fast) {
res = true;
break;
}
}
return res;
}
}
2. 找到环的入口-142
思路:
- 用哈希表存,找到第一个重复的节点
- 用快慢指针法,根据规则推算,从 head 到环入口的长度=相遇点到入环点的距离 + (n-1) 圈的环长
推导公式,可知:从 head 到入环点的距离,等于 fast和slow 第一次相遇点开始到入环点的距离 + (n-1) * 环长
也就是说:当 fast 和 slow 相遇时,ptr 从 head 出发,slow 从相遇点出发,第一次相遇必然在入环点
public static ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while (slow != null) {
if (fast.next == null || fast.next.next == null) {
return null;
}
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode ptr = head;
while (slow != ptr) {
slow = slow.next;
ptr = ptr.next;
}
return ptr;
}
}
return null;
}
3. 如何判断两个单向链表是否相交,如果相交,那么找出相交点-160
解法,如果相交,那么我们可以让链表 A 的尾部连接到链表 B 的 head,这样就会形成一个环。此时,判定是否相交就是找这个新链表的入环点。
/**
* 获取两个链表相交的点
* 假设链表中不存在环
* @param headA
* @param headB
* @return
*/
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
// 找到第一个链表的尾部
ListNode cur = headA;
while (cur.next != null) {
cur = cur.next;
}
// 将第一个链表的 tail 连接到第二个链表的 head,这样就形成了环
// 根据环形链表中的结论:从 head 出发到入环点的距离 = (n-1) * 环圈 + 相遇点-入环点
cur.next = headB;
// 用快慢指针法找到相遇点
ListNode slow = headA;
ListNode fast = headA;
while (slow != null && fast != null) {
if (slow.next == null || fast.next == null || fast.next.next == null) {
break;
}
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode ptr = headA;
// 从相遇点出发
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
cur.next = null;
return ptr;
}
}
cur.next = null;
return null;
}
4. 删除倒数第 n 个节点-19
在 O(n) 时间复杂度内删除倒数第 n 个节点
用快慢指针法,快指针先走 n 步,然后快慢指针一起走,当快指针到达链表尾部时,删掉慢指针所在节点;
/**
* 两个指针,fast 先走 n 步,然后 slow 出发,当 fast.next == null 时,删掉 slow
* @param head
* @param n
* @return
*/
public static ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) {
return null;
}
// 初始化 fast 和 head 两个指针,让 fast 先走 n 步
ListNode fast = head;
ListNode slow = head;
for (int i = 0; i < n - 1; i++) {
if (fast.next == null) {
return null;
}
fast = fast.next;
}
// 上面走了 n - 1 步,再走一步
if (fast.next == null) {
// 这一步表示达到末尾了,也就是要删除第一个元素
return head.next;
}
fast = fast.next;
// fast 和 slow 一起走,直到 fast 达到链表尾部,此时,slow 位置就是要删除的节点
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
if (slow.next != null) {
slow.next = slow.next.next;
}
return head;
}
经典问题
1. 反转链表-206
- 迭代:一次遍历,从 head 开始,顺序迭代,每次都将 head 的下一个节点放到链表头部,时间复杂度 O(n),空间复杂度 O(1)
- 递归:每次递归,将第一个节点放到最后;递归需要堆栈,空间复杂度变为 O(n);(所以对于这一题,还是迭代的方式很简洁)
迭代
public static ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 每次都将原来的 head 的下一个节点放到第一个节点
ListNode lastHead = head;
while (head.next != null) {
ListNode newHead = head.next;
head.next = head.next.next;
newHead.next = lastHead;
lastHead = newHead;
}
return lastHead;
}
递归
public static ListNode reverse(ListNode head) {
if (head.next == null) {
return head;
}
ListNode last = reverse(head.next);
head.next.next = head; // 把 head 放到 last 的尾部,这样 head 就完成了反转
head.next = null;
return last;
}
扩展:
参考:递归反转链表的一部分
1.1 反转链表前 N 个节点
- 迭代
- 递归
递归实现:
public static ListNode reverseN(ListNode head, int n) {
if (n == 1) {
// 结束递归
successor = head.next;
return head;
}
// 反转后面的元素
ListNode last = reverseN(head.next, n-1);
// 将 head 放到第 N + 1 节点前面, 原来的 head.next 已经变成了 last 的tail
head.next.next = head;
head.next = successor;
return last;
}
1.2 反转链表某一部分
/**
* 反转链表 m - n 中的节点,m >= 1, n <= 链表长度
* @return
*/
public static ListNode reverseMN(ListNode head, int m, int n) {
if (m == 1) {
// 此时相当于反转链表的前 n 个节点
return reverseN(head, n);
}
// 如果 m > 1,那么我们递归去反转 head.next
head.next = reverseMN(head.next, m - 1, n - 1);
return head;
}
1.3 k 个一组反转链表-25
LeetCode 25 题,难度:高
https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
思路:
- 反转前 k 个结点,然后递归反转 x * k+1 结点开始的 k 个结点
- 递归结束条件:直到链表剩余结点数小于 k
- 需要准备的方法:反转前 k 个结点
2. 移除链表元素-203
移除 val 等于指定值的节点,分为两种情况:
- 非 head 位置的元素,如果需要删除,只要 prev.next = cur.next 即可
- head 位置的元素,如果需要删除,那么就要将 head = head.next 才行
解决办法:
- 首先将位于最前面的需要删除的元素删除,确保之后要删除的节点不在 head 位置,然后遍历一遍即可
- 设置一个哨兵作为伪节点,让 sentinel.next = head,从 sentinel 位置开始遍历即可
第二种的代码:
public static ListNode removeElements(ListNode head, int val) {
ListNode sentinel = new ListNode(-1); // 哨兵
sentinel.next = head;
ListNode far = sentinel;
ListNode cur = head;
while (cur != null) {
if (cur.val == val) {
far.next = cur.next;
} else {
far = cur;
}
cur = cur.next;
}
return sentinel.next;
}
3. 奇偶链表-328
- [ ] 待优化
/**
* 奇偶转换
* 奇数位置的节点顺序在前,偶数位置的节点顺序在后
* @param head
* @return
*/
public static ListNode oddEvenList(ListNode head) {
if (head == null) {
return null;
}
ListNode evenHead = null;
ListNode cur = head;
while (cur != null) {
cur = cur.next; // 偶数
if (evenHead == null) {
evenHead = cur;
} else {
evenHead.next = cur;
}
if (cur == null) {
break;
}
cur = cur.next; // 奇数
}
return head;
}
4. 回文链表-234
- 方法 1: List 存储所有节点,两两对比, O(2*n) 时间复杂度,O(n) 空间复杂度
- 方法 2:直接反转整个链表,然后分别读两个链表;时间复杂度 O(n),空间复杂度 O(n)
- 方法 3:在方法2 基础上进行的优化 —— 用快慢指针找到中间节点,然后反转链表后半部分,然后让指针分别从 head 和 mid 出发来进行比较
方法 2,O(n) 时间复杂度的解法:
- 用快慢指针法找到中间节点,时间 n/2
- 反转链表后半部分, n/2
- 用双指针分别顺序遍历前半部分和后半部分,挨个比较,最坏情况是 O(n/2)
- 再次反转链表后半部分,以恢复链表 n/2
时间复杂度 O(n),空间复杂度 O(1)
class Solution {
/**
* 判定链表是否为回文字符串
*
* 1-2 false
* 1-2-2-1 true
* @param head
* @return
*/
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode mid = findMid(head);
// 反转链表后半部分
ListNode fast = reverseList(mid.next);
ListNode slow = head;
while (slow != mid.next && fast != null) {
// 注意判定条件,在节点为偶数的情况下,slow 最后等于 mid
// 在奇数情况下, slow.next 最后等于 mid -> 这种情况,要额外判断一下 fast 是否已经达到末尾了
if (slow.val != fast.val) {
reverseList(mid.next);
return false;
}
slow = slow.next;
fast = fast.next;
}
reverseList(mid.next);
return true;
}
/**
* 找到链表的中间节点
* 1-2-3-4 => 2
* 1-2-3 => 2
* @param head
* @return
*/
static ListNode findMid(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
if (fast != null) {
slow = slow.next;
}
}
return slow;
}
public static ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 1-2-3-4-5 -> 5-4-3-2-1
// 每次都将原来的 head 的下一个节点放到第一个节点
ListNode lastHead = head;
while (head.next != null) {
ListNode newHead = head.next;
head.next = head.next.next;
newHead.next = lastHead;
lastHead = newHead;
}
return lastHead;
}
}
扩展问题
1. 合并两个有序链表-21
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 思路:都插入到新链表中,这样只需要遍历 O(n)
ListNode sentinel = new ListNode(-1);
ListNode cur = sentinel;
ListNode a = l1;
ListNode b = l2;
while (true) {
if (a == null && b == null) {
break;
} else {
if (a == null) {
cur.next = b;
b = b.next;
} else if (b == null) {
cur.next = a;
a = a.next;
} else {
if (a.val <= b.val) {
cur.next = a;
a = a.next;
} else {
cur.next = b;
b = b.next;
}
}
cur = cur.next;
}
}
return sentinel.next;
}
2. 两数相加-2
题目:给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode sentinel = new ListNode(-1);
ListNode aCur = l1;
ListNode bCur = l2;
ListNode rCur = sentinel;
int carryNum = 0;
int thisSum = 0;
while (true) {
if (aCur == null && bCur == null) {
if (carryNum > 0) {
rCur.next = new ListNode(carryNum);
}
break;
}
thisSum = carryNum;
if (aCur == null) {
thisSum += bCur.val;
bCur = bCur.next;
} else if (bCur == null) {
thisSum += aCur.val;
aCur = aCur.next;
} else {
thisSum += (aCur.val + bCur.val);
aCur = aCur.next;
bCur = bCur.next;
}
carryNum = 0;
if (thisSum >= 10) {
thisSum = thisSum - 10;
carryNum = 1;
}
rCur.next = new ListNode(thisSum);
rCur = rCur.next;
}
return sentinel.next;
}
3. 扁平化多级双向链表-430
第一直觉:递归
为什么选择递归呢,因为每一个节点都可能有 child,而每一个 child 也都可能有自己的 child,子子孙孙无穷尽也。显然这里用递归是非常合适的。
/*
// Definition for a Node.
class Node {
public int val;
public Node prev;
public Node next;
public Node child;
};
*/
class Solution {
public Node flatten(Node head) {
if (head == null) {
return head;
}
Node next = null;
if (head.child == null) {
if (head.next != null) {
next = flatten(head.next);
}
} else {
Node oldNext = head.next;
next = flatten(head.child);
if (oldNext != null) {
Node newTail = next;
while (newTail.next != null) {
newTail = newTail.next;
}
newTail.next = oldNext;
oldNext.prev = newTail;
}
}
head.child = null;
head.next = next;
if (next != null) {
next.prev = head;
}
return head;
}
}
4. 复制带随机指针的链表-138
题目描述:链表中每个节点都有一个 random 指针,指向任意的其他节点或空节点。要求实现一个函数,实现链表的深拷贝。
思路:
- 用一个 map 存储原来节点和对应的拷贝节点,第一次遍历链表拷贝 val,第二次遍历链表拷贝 next 和 random
/*
// 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) {
HashMap<Node, Node> copyMap = new HashMap<>();
// copy val
Node cur = head;
while (cur != null) {
Node copy = new Node(cur.val);
copyMap.put(cur, copy);
cur = cur.next;
}
// copy next and random
cur = head;
while (cur != null) {
Node copy = copyMap.get(cur);
copy.next = copyMap.get(cur.next);
copy.random = copyMap.get(cur.random);
cur = cur.next;
}
return copyMap.getOrDefault(head, null);
}
}
5. 旋转链表-61
解法:形成环,然后找到新的 head 并断开环
public ListNode rotateRight(ListNode head, int k) {
if (k <= 0 || head == null) {
return head;
}
int size = 0;
ListNode tail = null;
ListNode cur = head;
while (cur != null) {
size++;
if (cur.next == null) {
tail = cur;
}
cur = cur.next;
}
// 变成环
tail.next = head;
// 在合适的位置断开环
int i = 0;
k = k % size; // 取余数
while (i < size - k) {
tail = tail.next;
i++;
}
ListNode newHead = tail.next;
tail.next = null;
return newHead;
}
One comment
吊人OωO