刷leetcode hot100返航必胜版--链表6/3
链表初始知识
链表种类：单链表，双链表，循环链表
链表初始化
struct ListNode{
int val;
ListNode* next;
ListNode(int x): val（x）,next(nullptr) {}
};
//初始化
ListNode* head = new ListNode(5);
删除节点、添加节点
考虑的边界
head==nullptr || head->next ==nullptr
处理链表的输入输出
// 本地测试代码 (main.cpp)
#include <iostream>
using namespace std;struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};// 粘贴修正后的Solution类
int main() {
// 创建链表 1->2->3->4->5
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
Solution sol;
ListNode* newHead = sol.reverseList(head);
// 打印结果: 5->4->3->2->1
while (newHead) {
cout << newHead->val << " ";
newHead = newHead->next;
}
return 0;
}
ListNode vs ListNode*
ListNode node; // 创建默认节点 (val=0, next=nullptr)
ListNode node2(5); // 创建 val=5 的节点
ListNode node3(10, &node); // 创建 val=10 并指向 node 的节点
ListNode* ptr = new ListNode(); // 动态创建节点
ListNode* ptr2 = new ListNode(20); // 动态创建 val=20 的节点
1.相交链表【没想明白】6/31h
160. 相交链表 - 力扣（LeetCode）
问题：没看懂其实找的是指针相同/地址相同，而不是数值相同
法一：哈希表，找b中指针在不在a里
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {//好奇怎么样处理输入//请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null //暴力解forfor//我才看懂这个是地址相同不是val相同ListNode*a = headA;ListNode*b = headB;unordered_set<ListNode*>set;while(a!=nullptr){set.insert(a);a = a->next;}while(b!=nullptr){if(set.find(b)!=set.end()){return b;}b = b->next;}return nullptr;}
};法二：类似数学发现
不相交：
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {//好奇怎么样处理输入//请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null //暴力解forfor//我才看懂这个是地址相同不是val相同ListNode*a = headA;ListNode*b = headB;while(!(a==nullptr && b==nullptr)){if(a == b){return a;}if(a!=nullptr){a = a->next;}else{a = headB;}if(b!=nullptr){b = b->next;}else{b = headA;}}return nullptr;}
};2.反转链表【30min】
206. 反转链表 - 力扣（LeetCode）
注意：qpr返回的是哪个，如何初始化
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {if(head == nullptr || head->next == nullptr){return head;}ListNode * p = head;ListNode * q = nullptr;ListNode * r;
//q,p,rwhile(p!=nullptr){r = p->next;p->next = q;q = p;p = r;}return q; }
};法二：递归【没咋看】
class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode newHead = reverseList(head.next);head.next.next = head;head.next = null;return newHead;}
}
3回文链表
234. 回文链表 - 力扣（LeetCode）
问题：原来想先把链表反转，然后遍历，看值是否相同。
但是其实反转之后，链表被覆盖了
所以可以找到链表中点，反转一半，然后遍历比较值
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverse(ListNode*head){if(head == nullptr || head->next == nullptr){return head;}ListNode* p = head;ListNode*q = nullptr;ListNode*r;//qprwhile(p != nullptr){//p != nullptrr = p->next;p->next = q;q = p;p = r;}return q;//返回的有问题}bool isPalindrome(ListNode* head) {//哈希表有问题，不是按照顺序判断的ListNode *p = head;int size = 0;while(p!=nullptr){p = p->next;size++;}int half = size/2;size = 0;p = head;while(size !=half){p = p->next;size++;}ListNode * head1 = reverse(p);//链表改变size = 0;while(size!=half){if(head->val != head1->val){return false;}size++;head = head->next;//忘记处理一般情况了head1 = head1->next;}return true;}
};4.环形链表
141. 环形链表 - 力扣（LeetCode）
法一：哈希表
问题：while(head!=nullptr && set.find(head)==set.end()){条件写错了：没到终点且元素没出现
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {if(head == nullptr){return false;}unordered_set<ListNode *>set;while(head!=nullptr && set.find(head)==set.end()){//set.find(head)==set.end()没找见set.insert(head);head = head->next;}if(head==nullptr){return false;}else{cout<<head->val;return true;}}
};法二：数学发现/双指针
每次移动差一个，若有圈，绕n圈后必然相见
灵神一语点醒梦中人：
这时用「相对速度」思考，乌龟不动，兔子相对乌龟每次只走一步，这样就可以看出兔子一定会和乌龟相遇了。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {if(head == nullptr ){return false;}ListNode* slow = head;ListNode* fast = head->next;while (slow != fast) {if (fast == nullptr || fast->next == nullptr) {return false;}slow = slow->next;fast = fast->next->next;}return true;}
};5.环形链表2
142. 环形链表 II - 力扣（LeetCode）
法一哈希表
法二数学发现/双指针[floyd判圈算法]
快的走了：a+d+kc
慢的走了：a+d
首先，k= 1,
a+d+c = 2(a+d)
c = a+d
求a，
关键在于：c-d = a
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head == nullptr || head->next ==nullptr){return nullptr;}ListNode *low = head->next;ListNode* fast = head->next->next;//同一起点//数组中第 k 个最大的元素//求awhile(fast!= nullptr && low!=fast){//初始都是head，不合适low = low->next;fast = fast->next ? fast->next->next:nullptr;//写反了}if(low == fast){while(head!=low){head = head->next;low = low->next;}return low;}else{return nullptr;}}};