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;//~
            }
            else
                cur = 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;//~同上
            }
            else
                cur = 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; 
    }

};

后来，看到了官方题解。

官方题解中，使用了