链表初始知识

链表种类：单链表，双链表，循环链表

 

链表初始化 

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）

/*** 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;}
}