【数据结构】励志大厂版·初阶（复习+刷题）单链表

目录

1. 单链表基础概念回顾
2. 单链表的常见操作详解
3. 典型面试题目及解析
4. 刷题推荐及题目思路点拨
5. 总结与面试技巧

1️⃣ 单链表基础概念回顾

• 定义：链表是一种线性数据结构，由一系列节点组成，每个节点包含数据域和指向下一个节点的指针（单链表只指向下一个节点）。
• 特点：动态存储，插入和删除操作灵活，不连续内存空间。
• 单链表节点结构（C++示例）：

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

2️⃣ 单链表的常见操作详解

反转链表示例代码（C++）

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

3️⃣ 典型面试题目及解析

题目1：删除链表的倒数第N个节点

• 思路：双指针法，先让快指针走n步，然后快慢指针一起走，快指针到末尾时慢指针刚好指向倒数第n+1个节点。
• 示例代码：

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* fast = &dummy;
    ListNode* slow = &dummy;

    for (int i = 0; i <= n; i++) fast = fast->next;

    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }

    ListNode* toDelete = slow->next;
    slow->next = slow->next->next;
    delete toDelete;

    return dummy.next;
}

题目2：合并两个有序链表

• 思路：用两个指针分别遍历两个链表，比较节点大小，依次链接。
• 示例代码：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;

    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

4️⃣ 刷题推荐及题目思路点拨

5️⃣ 总结与面试技巧

• 理解指针操作是单链表刷题的核心，边写边画图帮助理清指针关系。
• 多练习快慢指针技巧，能解决链表中很多经典难题。
• 养成写“哨兵节点”习惯，简化边界条件处理。
• 刷题时注意内存管理，避免野指针和内存泄漏。
• 模拟真实面试环境，练习代码思路清晰表达。