← 返回学习路线

SYSTEM

链表

八股1.2 链表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 三个属性为节点值设置类型特定函数,所以链表可以保存各种不同类型的值