鏈表初始知識

鏈表種類：單鏈表，雙鏈表，循環鏈表

?

鏈表初始化?

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

?