当前位置：首页 > news >正文

LeetCode 热题 100 | 链表（上）

news 来源：原创 2024/5/20 14:37:22

1 基础知识

1.1 空指针

1.2 结构体

1.3 指针访问

1.4 三目运算符

2 160. 相交链表

3 206. 反转链表

4 234. 回文链表

菜鸟做题第三周，语言是 C++

1 基础知识

1.1 空指针

使用 nullptr 来判断是否为空指针：

if (headA == nullptr)

“NULL 在 C++ 中就是 0，这是因为在 C++ 中 void* 类型是不允许隐式转换成其他类型的，所以之前 C++ 中用 0 来代表空指针，但是在重载整型的情况下，会出现上述的问题。所以，C++11 加入了 nullptr，可以保证在任何情况下都代表空指针，而不会出现上述的情况，因此，建议以后还是都用 nullptr 替代 NULL 吧，而 NULL 就当做 0 使用。”

摘自博客：C++ 中 NULL 和 nullptr 的区别

1.2 结构体

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

val 和 next 都是结构体 ListNode 中的元素
val 表示当前链表节点的值
next 表示指向下一个链表节点的指针
ListNode(int x) : val(x), next(NULL) {} 是初始化方法

1.3 指针访问

ListNode * p;p->val;  // 访问值
p->next;  // 访问下一节点指针

1.4 三目运算符

pA = pA == nullptr ? headB : pA->next;

其中，“?” 前的是判断条件，“?” 后的是两个选项，“:” 前的是条件成立时选择的选项，“:” 后的是条件不成立时选择的选项。这里的 “pA == nullptr” 是判断条件，“headB” 是 “pA == nullptr” 成立时 “pA” 等于的值，“pA->next” 是 “pA == nullptr” 不成立时 “pA” 等于的值。

三目运算符不是为了装逼用的，真的可以在很多情况下简化判断结构。

2 160. 相交链表

妈呀，这是我大一下程算课期末的真题

解题思路：

假设蓝色段的长度为 a，绿色段的长度为 b，黄色段的长度为 c 。定义 pA 和 pB 两个指针，pA 遍历完 a + c 后遍历 b，pB 遍历完 b + c 后遍历 a，判断：

若 pA 和 pB 相遇且节点不为空，则表明两条链表相交
若 pA 和 pB 未相遇或节点为空，则表明两条链表不相交

这种解法用到了一点数学思想：

$a+b+c$

即 pA 和 pB 最终都会到达同一位置，它们在该位置指向的节点是否一致决定了链表是否相交。

如有疑问请参考官方题解，它的分情况讨论更加详细。

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if (headA == nullptr || headB == nullptr) {return nullptr;}ListNode * pA = headA, * pB = headB;while (pA != pB) {pA = pA == nullptr ? headB : pA->next;pB = pB == nullptr ? headA : pB->next;}return pA;}
};

3 206. 反转链表

解题思路：把所有节点的 next 指针全部反向即可。

思路说明图：

对于这种反转问题，核心思想就是把已经遍历过的、但还需要用到的位置保存下来。

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode * prev = nullptr;ListNode * curr = head;while (curr) {ListNode * next = curr->next;curr->next = prev;prev = curr;curr = next;} return prev;}
};

4 234. 回文链表

解题思路：

遍历链表，把所有 val 存入一个数组中
遍历数组的前半段，判断里面的 val 是否和后半段的 val 对称

class Solution {
public:bool isPalindrome(ListNode* head) {ListNode * p = head;vector<int> vals;while (p) {vals.push_back(p->val);p = p->next;}for (int i = 0; i < vals.size() / 2 + 1; ++i) {if (vals[i] != vals[vals.size() - i - 1]) return false;}return true;}
};