LeetCode 热门题库 100 链表第一课
目录
1 基础知识
1.1 空指针
1.2 结构体
1.3 指针访问
1.4 三目运算符
2 160. 相交链表
2.1 解法一
2.2 解法二
3 206. 反转链表
3.1 解法一：双指针
3.2 解法二：递归
4 234. 回文链表
菜鸟做题第三周，语言是 C++
1 基础知识
1.1 空指针
使用 nullptr 来判断是否为空指针：
if (headA == nullptr)在 C++ 中, NULL 实际上等同于数值 0。这是因为类型 void* 在设计上是被禁止进行隐式转换到其他类型的操作。因此，在早期版本的 C++ 中, 常常使用数值 0 来代表空指针。然而, 当对整型操作符进行重载时, 这种表示方法会导致矛盾。自 C++11 推出以来, 程序员可以通过引入关键字 'nullptr' 来明确标识空指针。因此, 建议大家今后尽量使用 'nullptr' 来代替 'NULL', 这样可以避免混淆的同时将 'NULL' 视为与数值 0 等价使用
摘自博客：C++ 中 NULL 和 nullptr 的区别
摘自博客：C++ 中 NULL 和 nullptr 的区别
摘自博客：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设置为空。
1.3 指针访问
ListNode * p;
p->val; // 访问值
p->next; // 访问下一节点指针1.4 三目运算符
pA = pA == nullptr ? headB : pA->next;在该逻辑中，在处理链表合并时会采用如下形式：首先会检查当前节点的状态（即判断逻辑），若当前节点为空指针（即"pA为空指针"），则会选择headB作为后续操作的基础；反之，则会将当前节点指向其下一个节点（即"pA指向节点的下一个节点"）以完成合并过程。
三目运算符不是为了装逼用的，真的可以在很多情况下简化判断结构。
2 160. 相交链表
2.1 解法一
妈呀，这是我大一下程算课期末的真题
解题思路：
设蓝色区域宽度为a厘米、绿色区域宽度为b厘米、黄色区域宽度为c厘米。设定两个指针变量pA和pB（其中参数可选）。判断流程：首先完成从位置0到a+c的整体移动后转而完成对b区间的访问；其次完成从位置0到b+c的整体移动后转而完成对a区间的访问；
- 如果pA与pB会合，并且存在非空节点，则可推知两条链表相交。
- 如果pA与pB不会合或者无非空节点，则可推知两条链表不相交。
这种解法用到了一点数学思想：
也就是说 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;
}
};2.2 解法二
二刷 Hot100 之 Python3 写法
核心思想：查重
- 将所有指向的节点存入集合。
- 逐一访问头B指向的链表，并利用集合对所有节点进行检查。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
occ = set()
p = headA
while p != None:
occ.add(p)
p = p.next
q = headB
while q != None:
if q in occ:
return q
q = q.next
return None3 206. 反转链表
3.1 解法一：双指针
解题思路：把所有节点的 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;
}
};3.2 解法二：递归
二刷 Hot100 之 Python3 写法
核心思想：
- 假设目前阶段中，在位于节点k后续的位置上已完成链表反转操作；
- 正在将节点k纳入已完成反向操作的链表部分进行处理；
- 处理完成后会返回至节点k-1对应的递归层级，并在此基础上执行相同操作。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head == None or head.next == None:
return head
newHead = self.reverseList(head.next)
head.next.next = head
head.next = None
return newHead4 234. 回文链表
解题思路：
- 遍历该链表以获取每个节点的 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;
}
};二刷 Hot100 之 Python3 写法
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
nums = []
p = head
while p:
nums.append(p.val)
p = p.next
return nums == nums[::-1]