刷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;}}};