链表总结|dc的house

链表是数据结构中的重要内容，也是面试中的高频考点。本文将从链表的基础知识出发，逐步深入，结合经典题目和代码实现，帮助你全面掌握链表的操作技巧。

链表的理论基础

链表的种类

链表主要分为以下几种：

单链表：每个节点包含数据和指向下一个节点的指针。
双链表：每个节点包含数据、指向前一个节点的指针和指向下一个节点的指针。
循环链表：尾节点指向头节点，形成一个环。

链表的存储方式

链表的节点在内存中是分散存储的，通过指针连接在一起。与数组不同，链表不需要连续的内存空间。

链表的操作

链表的核心操作包括：

增：在链表中插入节点。
删：删除链表中的节点。
改：修改链表中的节点值。
查：查找链表中的节点。

数组与链表的性能对比

数组：适合随机访问，插入和删除效率低。
链表：适合频繁插入和删除，随机访问效率低。

链表经典题目

1. 虚拟头结点

虚拟头结点是链表操作中的一个重要技巧，可以简化对头结点的处理。

代码实现

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class MyLinkedList {
private:
    ListNode* dummyHead; // 虚拟头结点
    int size; // 链表长度

public:
    MyLinkedList() {
        dummyHead = new ListNode(0); // 初始化虚拟头结点
        size = 0;
    }

    // 获取第index个节点的值
    int get(int index) {
        if (index < 0 || index >= size) return -1;
        ListNode* cur = dummyHead->next;
        while (index--) cur = cur->next;
        return cur->val;
    }

    // 在链表头部插入节点
    void addAtHead(int val) {
        ListNode* newNode = new ListNode(val);
        newNode->next = dummyHead->next;
        dummyHead->next = newNode;
        size++;
    }

    // 在链表尾部插入节点
    void addAtTail(int val) {
        ListNode* newNode = new ListNode(val);
        ListNode* cur = dummyHead;
        while (cur->next) cur = cur->next;
        cur->next = newNode;
        size++;
    }

    // 在第index个节点前插入节点
    void addAtIndex(int index, int val) {
        if (index > size) return;
        ListNode* newNode = new ListNode(val);
        ListNode* cur = dummyHead;
        while (index--) cur = cur->next;
        newNode->next = cur->next;
        cur->next = newNode;
        size++;
    }

    // 删除第index个节点
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        ListNode* cur = dummyHead;
        while (index--) cur = cur->next;
        ListNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        size--;
    }
};

2. 反转链表

反转链表是链表操作中的经典问题，常见解法有迭代法和递归法。

迭代法

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* cur = head;
    while (cur) {
        ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

递归法

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

3. 删除倒数第N个节点

使用双指针技巧可以高效删除倒数第N个节点。

代码实现

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummyHead = new ListNode(0);
    dummyHead->next = head;
    ListNode* fast = dummyHead;
    ListNode* slow = dummyHead;

    // 快指针先走n步
    while (n-- && fast) fast = fast->next;

    // 快慢指针一起走
    while (fast->next) {
        fast = fast->next;
        slow = slow->next;
    }

    // 删除节点
    ListNode* tmp = slow->next;
    slow->next = slow->next->next;
    delete tmp;

    return dummyHead->next;
}

4. 链表相交

找到两个链表的交点（内存地址相同的节点）。

代码实现

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    ListNode* curA = headA;
    ListNode* curB = headB;

    // 计算两个链表的长度
    int lenA = 0, lenB = 0;
    while (curA) { lenA++; curA = curA->next; }
    while (curB) { lenB++; curB = curB->next; }

    // 长链表先走
    curA = headA;
    curB = headB;
    if (lenA > lenB) {
        int gap = lenA - lenB;
        while (gap--) curA = curA->next;
    } else {
        int gap = lenB - lenA;
        while (gap--) curB = curB->next;
    }

    // 一起走，直到相遇
    while (curA != curB) {
        curA = curA->next;
        curB = curB->next;
    }
    return curA;
}

5. 环形链表

判断链表是否有环，并找到环的入口。

代码实现

ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    // 判断是否有环
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }

    // 无环
    if (!fast || !fast->next) return nullptr;

    // 找到环的入口
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}