SYSTEM
链表
src/content/notes/system/链表.md 1.2 链表
链表题的套路是:画清指针走向、用 dummy 头节点简化头插、用快慢指针解决环与中点问题。
反转链表(迭代 + 递归)
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
// 迭代:三指针逐个翻转
public ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
// 递归:先反转后面的,再把当前接到末尾
public ListNode reverseListRec(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverseListRec(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
合并两个有序链表(力扣 21)
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; }
else { cur.next = l2; l2 = l2.next; }
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2; // 接上剩余
return dummy.next;
}
}
环检测(力扣 141 快慢指针)
class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true; // 快慢相遇则有环
}
return false;
}
}
面试题:“如何检测链表有环?”
用快慢指针:慢指针走一步、快指针走两步,若存在环,快指针一定会从后面追上慢指针(相遇);若快指针走到 null 则无环。原理是若有环,快指针每轮相对慢指针多走一步,差距会逐步缩小到 0。要找环入口,相遇后让一个指针回到头,两指针同速再走,再次相遇点即入口。
补充材料 · 链表
链表
链表提供了高效的节点重排能力,C 语言并没有内置这种数据结构,所以 Redis 构建了链表数据类型
链表节点:
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value
} listNode;
多个 listNode 通过 prev 和 next 指针组成双端链表:

list 链表结构:提供了表头指针 head 、表尾指针 tail 以及链表长度计数器 len
typedef struct list {
// 表头节点
listNode *head;
// 表尾节点
listNode *tail;
// 链表所包含的节点数量
unsigned long len;
// 节点值复制函数,用于复制链表节点所保存的值
void *(*dup) (void *ptr);
// 节点值释放函数,用于释放链表节点所保存的值
void (*free) (void *ptr);
// 节点值对比函数,用于对比链表节点所保存的值和另一个输入值是否相等
int (*match) (void *ptr, void *key);
} list;

Redis 链表的特性:
- 双端:链表节点带有 prev 和 next 指针,获取某个节点的前置节点和后置节点的时间复杂度都是 O(1)
- 无环:表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL,对链表的访问以 NULL 为终点
- 带表头指针和表尾指针: 通过 list 结构的 head 指针和 tail 指针,获取链表的表头节点和表尾节点的时间复杂度为 O(1)
- 带链表长度计数器:使用 len 属性来对 list 持有的链表节点进行计数,获取链表中节点数量的时间复杂度为 O(1)
- 多态:链表节点使用 void * 指针来保存节点值, 并且可以通过 dup、free 、match 三个属性为节点值设置类型特定函数,所以链表可以保存各种不同类型的值