链表核心概念与经典算法题解析

链表核心概念与经典算法题解析

一、前言

接下来进入基础数据结构部分。

二、链表

2.1 本质

链表就是把数据离散开。

2.2 误区

头结点：不存任何数据
首元结点：存放着第一个数据

2.3 思路

• 根据题意选择合适的链表类型，如：单链表（带或不带头节点）
• 模拟遍历或快慢指针思想

2.4 题型

2.4.1 LeetCode

• 206. 反转链表（头插法）两种思路：
  • 头插法：p = q; q = p->next; p->next = NULL; 从第一个节点开始，挨个摘下每一个节点，摘下后用头插法建立新的链表

142. 环形链表 II题意：判断有没有环以及从哪个节点开始进入环的（类似于跑步套圈的情况）。思路：如果有环，总有一天快指针会和慢指针相遇，并且快慢指针永远不会跑到空的地方；如果没环，快指针会很快指向空的地方。如何看从哪里开始进入环呢？快慢指针：快慢指针相遇一定是在圈里相遇。假设相遇点是 x，f 指针走的快，先绕圈；s 指针走的慢，后开始绕圈。f 指针走了 a + b，继续走；s 指针先走了 a，进入圈刚走了 b 就和 f 指针相遇了。此时，f 已经跑了 n 圈，a + n * (b + c) + b。如图：

快指针和慢指针走，当它们两个相遇的时候，快指针就停下来，在用一个慢指针从起点开始走，慢指针继续走，当第一个慢指针又和第二个慢指针相遇的时候，就是开始进入圈的点。代码：

// 判断成环
#include <iostream>
#include <algorithm>
using namespace std;

typedef struct ListNode {
    int val;
    ListNode *next;
} ListNode;

ListNode* detectCycle(ListNode* head) {
    ListNode* f = head;
    ListNode* s = head;
    while (f != nullptr) {
        s = s->next;
        if (f->next == nullptr) {
            return nullptr;
        }
        f = f->next->next;
        if (s == f) {
            ListNode* p = head;
            while (p != s) {
                p = p->next;
                s = s->next;
            }
            return p;
        }
    }
    return nullptr;
}

int main() {
    int n, x;
    // 建立单链表
    cin >> n;
    ListNode* head = nullptr;
    ListNode* r = nullptr;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        ListNode* s = (ListNode*)malloc(sizeof(ListNode));
        s->val = x;
        s->next = nullptr;
        if (i == 1) {
            head = s;
            r = s;
        } else {
            // 尾插法
            r->next = s;
            r = s;
        }
    }
    cin >> x;
    ListNode* ans = detectCycle(head);
    if (ans == nullptr) {
        cout << "无环" << endl;
    } else {
        cout << ans->val << endl;
    }
    return 0;
}

LCR 140. 训练计划 II题意：给一个链表，找倒数第 cnt 个数据。思路：快慢指针。

ListNode *f = head;
ListNode *s = head;
while (f->next != nullptr) {
    // f 先走，s 和 f 相距 cnt 个
    if (cnt > 1) {
        f = f->next;
        cnt--;
        continue;
    }
    // s 和 f 一起走
    s = s->next;
    f = f->next;
}
// 最后 s 指向的就是第 cnt 个
return s;

双指针：

t 指针：防止后面的部分丢失
p 指针：遍历链表
q 指针：为了使 p 指向前面的节点，q 指向前面的节点

代码：

// 反转链表——在原链表进行操作 (无 malloc)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef struct ListNode { // 定义链表节点
    int val;
    ListNode *next;
} ListNode;

ListNode* reverseList(ListNode* head) {
    ListNode* p = head;
    ListNode* q = nullptr;
    while (p != nullptr) {
        ListNode* t = p->next; // 防止后面的丢失
        p->next = q; // 往前指
        q = p; // 顺序不能反
        p = t;
    }
    return q;
}

int main() {
    int n, x;
    cin >> n;
    ListNode* head = nullptr;
    ListNode* r = nullptr;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        ListNode* s = (ListNode*)malloc(sizeof(ListNode));
        s->val = x;
        s->next = nullptr;
        if (i == 1) {
            head = s;
            r = s;
        } else {
            // 尾插法
            r->next = s;
            r = s;
        }
    }
    head = reverseList(head);
    ListNode* s = head;
    while (s != nullptr) {
        cout << s->val << ;
        s = s->next;
    }
     ;
}

2.4.2 洛谷

• P1996 约瑟夫问题

2.5 补充

2.5.1 静态链表

用数组描述的链表（结构体数组）

2.5.2 跳表

在有序链表的基础上增加了'跳跃'的功能，对有序的链表实现二分查找功能。多层链表，每一层都有序，最下面的链表是最原始的链表（包括所有数据），从下往上节点折半提取元素上移。

三、小结

本篇结合经典题单、洛谷官方书籍等资料整理。