leetcode-链表

链表是一个用指针串联起来的线性结构，每个结点由数据域和指针域构成，指针域存放的是指向下一个节点的指针，最后一个节点指向NULL，第一个结点称为头节点head。

常见的链表有单链表、双向链表、循环链表。双向链表就是多了一个pre指针，头节点的pre指向NULL。循环链表就是尾节点的next指向了头节点，可以用来解决约瑟夫问题。

链表内存为节点间不连续，节点内连续。适用于解决数据长度不固定，不经常查找，经常增删的问题。

要学会自己定义struct ListNode，并且要知道构造函数自己写完怎么用（使用ListNode *node = new ListNode(3)）这样就可以new一个ListNode出来让node指向了。

1.移除元素 Leetcode203. 分为虚拟节点和不使用虚拟节点

在这一题里我终于体会到了tmp=nullptr的用处。

代码随想录里明明只使用了delete tmp，但是我没有用tmp = nullptr 还是报了内存的错误，下面这样写才通过，但是看起来明明不对。

/*** 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* removeElements(ListNode* head, int val) {// 2. 使用虚拟头节点while(head!=nullptr && head->val ==val){ListNode* tmp = head;//内存~head = head->next;delete tmp;//内存~}ListNode* cur = head;while(cur != nullptr && cur->next != nullptr){if(cur->next->val == val){ListNode* tmp = cur->next;//~cur->next = cur->next->next;delete tmp;//~}elsecur = cur->next;}return head;  }
};

/*** 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* removeElements(ListNode* head, int val) {// 2. 使用虚拟头节点ListNode *dummynode = new ListNode();dummynode->next = head;ListNode *cur = dummynode;while(cur != nullptr && cur->next != nullptr){if(cur->next->val == val){ListNode* tmp = cur->next;//考虑一下内存，不考虑也没事，只是大一些cur->next = cur->next->next;delete tmp;//~同上}elsecur = cur->next;}return dummynode->next;  }
};

这里要注意我的虚拟头节点也是一个指针类型的，因为我要使用到dummynode->next这种操作，仅仅是指向虚拟头结点的一个指针而已。我一开始用的是ListNode dummynode = new ListNode()，这是不对的。

[注意]通常情况下，在执行了 delete 操作之后，将指针置为 nullptr 是不必要的，因为你不应该在删除后继续使用已经释放的内存。这不是内存管理的原则之一。这里，delete之前要暂存一下删的东西地址，不然不知道删啥。

2.设计链表20230828

本题给了ListNode的节点定义，需要写MyLinkedList中的构造函数、get、addAtHead、addAtTail、addAtIndex、deleteAtIndex。

需要注意的是：第一，写错了什么东西--。我本来是index--，误写成tmp--，找了半天也没发现哪里错。

在这里插入图片描述

第二个写错的是这里：

在这里插入图片描述

这里写错了，其实index=0也可以删，就是把头节点删掉。这里错误导致我有三个用例不通过，都是delete头节点的。改成>=0就行了。

这一题熟悉了链表的操作，并且深刻体会了虚拟头节点的妙用。

3.反转链表LCR024 20230829

双指针法，清晰易懂：

/*** 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) {ListNode *pre = nullptr;ListNode *cur = head;while(cur){ListNode *tmp = cur -> next; cur -> next = pre;pre = cur;cur = tmp;}return pre;}
};

代码真是超简单，但是记得我们本来只有prev和current，是因为要存断裂开来的current才引入了temp。

并且，记得prev最终指向尾节点，cur最终指向尾节点后的nullptr，所以while的条件是cur！=nullptr。当等于空，直接可以返回，返回的头节点就是prev。

时间复杂度O(n)，空间复杂度O(1)

class Solution {
public:ListNode* reverseList(ListNode* head) {return reverse(nullptr,head);}ListNode* reverse(ListNode *pre, ListNode *cur){if(cur == nullptr)return pre;else{ListNode *temp = cur->next; cur -> next = pre;return reverse(cur, temp);}}
};

以上是递归写法，是双指针法的变体。

4. 两两交换链表中的节点Leetcode24. 20230901

在这里插入图片描述

/*** 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* swapPairs(ListNode* head) {//定义虚拟头节点ListNode *dummynode = new ListNode();dummynode -> next = head;ListNode *cur = dummynode;while(cur -> next != nullptr && cur -> next -> next != nullptr){ListNode *tmp = cur -> next;ListNode *tmp1 = cur -> next -> next -> next;cur -> next = cur -> next -> next;cur -> next -> next = tmp;tmp -> next = tmp1;cur = cur -> next -> next;}return dummynode -> next;}
};

这一题画图非常重要！

5. 删除链表的倒数第N个节点：删除某节点，指针需要跑到节点前面20230902

本题是快慢指针的经典使用！

/*** 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* removeNthFromEnd(ListNode* head, int n) {       ListNode *dummynode = new ListNode(); dummynode->next = head;ListNode *fast = head;ListNode *slow = dummynode;while(n-- && fast != nullptr){fast = fast->next;}while(fast != nullptr){fast = fast->next;slow = slow->next;}ListNode *tmp = slow->next;slow->next = slow->next->next;delete tmp;return dummynode->next;}
};

时间复杂度：O(n)，空间复杂度：O(1)

6. 链表相交面试题 02.07. 重点在于尾部对齐思想和非值相等20230902

尾部对齐这个没啥好说的，跟上题快慢指针一样思想记住就行

非值相等……简单来说就是我做题的时候以为下面这个示例应该1的时候就是相交的，其实测试用例应该是真给了两个相交链表，导致值相等的时候不一定相交，反而是直接判断指针curA!= curB相等才对。

在这里插入图片描述

/*** 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) {// 尾部对齐int lengthA = 0, lengthB = 0;ListNode *curA = headA, *curB = headB;while (headA != nullptr){headA = headA->next;lengthA++;}while (headB != nullptr){headB = headB->next;lengthB++;}if(lengthA > lengthB){int tmp = lengthA - lengthB;while(tmp--){curA = curA->next;} }else{int tmp = lengthB - lengthA;while(tmp--){curB = curB->next;} }// 移动指针找交点while(curA != nullptr && curA!= curB)//本来写的是curA->val != curB->val{curA = curA->next;curB = curB->next;}return curA;}
};

7. 环形链表II Leetcode142. 20230903

本题主要是数学证明居多。

这一题是这两篇唯一让我觉得有些心虚的，因为这个数学证明我自己肯定不会去想出来，让我们来看一下本题的思路：

在这里插入图片描述

/*** 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) {ListNode *fast = head;ListNode *slow = head;while(fast != nullptr  && fast->next !=nullptr){fast = fast->next ->next;slow = slow->next;if(fast == slow){ListNode *index1 = fast;ListNode *index2 = head;while(index1 != index2){index1 = index1->next;index2 = index2->next;}return index1;}}return nullptr;}
};

首先是快慢双指针从头开始，快指针到空就肯定无环；然后快指针两倍速入环，慢指针跟着一倍速入，慢指针走不到一圈必被快指针追上（考虑最坏情形，慢指针刚入，快指针刚比他快一格；当慢指针走完1环，快指针肯定走完2环。所以，慢在走1环的中途肯定被追上。）

我们列出的数学式子是2(x+y)=x+y+n(y+z)，注意这个2，就是因为快指针两格两格跨，又跟慢指针同时触发，所以是走了慢指针两倍距离。然后可以看到x=(n-1)(y+z)+y

那么如果我们要求入环点，就是求这个x。考虑被追上的这个情形下，正好有了y的尾部，那么走x与从y走最终就会在y头部相遇，这个从刚刚的式子可以几何理解，不论多走几圈，最终都是在y头部相遇，那么就得到了最后的点。[对于这一段真的是有点心虚，自己推不出来，笨笨again]

链表到此就结束了，说谢谢随想录。

8. 两数相加 leetcode2. 20231025

时隔一个月，在leetcode题单上看到这个第二题，是之前被我看过、提交过、放弃过的题，就在学会链表之后自己尝试了一下，调试了很多遍，好在最后通过了。但是，我并不知道这一题dummynode有什么用，也忘记了怎么写，并且忘记了如何优雅地循环新增node，所以只能抱着“节省空间”的想法，基于一个链表去进行求和，写出了如下丑陋冗余的代码：

/*** 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* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode *node = l2;ListNode *result = l2;bool carry = 0;while(l1 != nullptr && l2 != nullptr){int temp = l1->val + l2->val + carry;carry = 0;l1 = l1->next;l2 = l2->next;if(temp > 9){carry = 1;}node->val = temp % 10;if(l2 != nullptr)node = node->next;}if(l1 == nullptr && l2 == nullptr && carry == 1){ListNode *tailnode = new ListNode();tailnode->val = 1;node->next = tailnode;             }while(l1 != nullptr){node -> next = l1;node = node->next;int temp = l1->val + carry;carry = 0;l1 = l1->next;if(temp > 9){carry = 1;}node->val = temp % 10;if(l1 == nullptr && carry == 1){ListNode *tailnode = new ListNode();tailnode->val = 1;node->next = tailnode;             }}while(l2 != nullptr){int temp = l2->val + carry;carry = 0;l2 = l2->next;if(temp > 9){carry = 1;}node->val = temp % 10;if(l2 == nullptr && carry == 1){ListNode *tailnode = new ListNode();tailnode->val = 1;node->next = tailnode;             }node = node->next;}return result; }};

后来，看到了官方题解。

官方题解中，使用了