24、两两交换链表中的节点

·模拟节点交换

---

题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/

思路：循环中两两交换
   手写模拟一下交换的过程就比较容易了
   下图是我写的模拟过程：

 
代码实现：中规中矩地模拟就完事
     时间复杂度O(n)
     空间复杂度O(1)

/**
 * 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* cur =head;
        ListNode* per =new ListNode();
        ListNode* k = new ListNode();
        bool t=false;
        while(cur!=nullptr&&cur->next!=nullptr){//有可以进行交换的节点
            k=cur->next;//per要指向cur->next,先用k存cur->next
            cur->next=k->next;//改变cur的指针域
            per->next=k;
            per=per->next;
            per->next=cur;
            if(!t){//注意，当头两个节点进行交换后，head也需要进行交换
                head=per;
                t=true;
            }
            per=cur;
            cur=cur->next;          
        }
        return head;
    }
};

收获摘要：carl哥的方法用了虚拟头节点，我没用虚拟头节点，写下来还比较顺畅，就是要注意返回的head因为交换，要改变。

学习的文章链接：https://programmercarl.com/0024.两两交换链表中的节点.html#_24-两两交换链表中的节点

19、删除链表的倒数第N个节点

·链表长度计算，双指针更快

---

单链表倒着数真是吃饱没事干，正着数再减一减就可以了

题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

思路：先计算链表的总长度
   然后算出正着数是第几个
   删除节点

代码实现：
     时间复杂度O(n)
     空间复杂度O(1)

/**
 * 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) {
        int m=1;//计数器
        ListNode* phead=new ListNode(0,head);//虚拟头节点
        ListNode* cur=phead->next;
        while(cur->next!=nullptr){//计算链表长度
            cur=cur->next;
            m++;
        }
        m=m-n;//从左至右第m个
        cur=phead;
        while(m>0){
            cur=cur->next;
            m--;
        }
        ListNode* d=cur->next;
        cur->next=cur->next->next;
        delete d;
        return phead->next;
    }
};

收获摘要：设置虚拟头节点方便处理针对头节点的情况，
     比如删掉头节点后，就不能返回头节点，
     但是可以返回虚拟头节点的指针域doge

     此题用双指针法可以只扫一遍链表，类似于滑块doge
     双指针yyds！精简了计算666
     ps：双指针的代码可以在文章链接里参考，就不ctrl+v了哈哈哈
     复习的时候可以用双指针实现

学习的文章链接：https://programmercarl.com/0019.删除链表的倒数第N个节点.html#_19-删除链表的倒数第n个节点

面试题02.07.链表相交

·世界线收束doge

---

就是说收束前两条链表不一样长~

题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

前提：不存在环
   相交点不是数值相等，而是指针(节点)相等

思路：算出两条链表的长度
   两条链表相交节点之后的长度相等
   进行一个右对齐的操作，然后往后找相交节点

代码实现：
     时间复杂度O(n)
     空间复杂度O(1)

/**
 * 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) {
        ListNode* curA=new ListNode(0,headA);
        ListNode* curB=new ListNode(0,headB);
        int la=0;
        int lb=0;
        int l;
        while(curA->next!=NULL){
            curA=curA->next;
            la++;
        }
        curA=headA;
        while(curB->next!=NULL){
            curB=curB->next;
            lb++;
        }
        curB=headB;
        l=(la>lb)?la:lb;
        for(int i=1;i<=l;i++){
            if(curA==curB){
                return curA;
            }
            else if(la>lb){
                curA=curA->next;
                la--;
            }
            else if(la<lb){
                curB=curB->next;
                lb--;
            }
            else{
                curA=curA->next;
                curB=curB->next;
            }
        }
        return NULL;
    }
};

收获摘要：虚拟头节点方便考虑头节点的情况（梅开n度），
     链表长度不一样就把它拉到一样，然后就一路畅通了。

学习的文章链接：https://programmercarl.com/面试题02.07.链表相交.html#思路

142、环形链表Ⅱ

·双指针+一些数学运算

---

他跑、她走，她被追~此处应有bgm：恋爱循环doge

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/

思路：双指针，一快一慢
   每次快指针比慢指针还要快一步 (just one)
   快指针先进入循环（循环ing）
   直到两个指针相遇（！！）
   经过一些数学运算
   请返回：循环入口

代码实现：
     时间复杂度O(n)
     空间复杂度O(1)

/**
 * 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) {
        int xy=0;
        ListNode* fast=head;
        ListNode* slow=head;
        if(head==NULL)return NULL;
        while(fast->next!=NULL&&fast->next->next!=NULL){
            fast=fast->next->next;
            slow=slow->next;
            xy++;
            if(slow==fast){//两个指针相遇了
                slow=head;//一个退回原点，另一个从相遇节点继续循环
                while(slow!=fast){
                    fast=fast->next;
                    slow=slow->next;
                }
                return slow;//再相遇就是循环入口节点
            }
        }
        return NULL;
    }
};

收获摘要：双指针yyds（这句话我已经说了千百遍~）
     理解 x：头节点-循环入口节点
        y：循环入口节点-相遇节点
        z：相遇节点-循环入口节点
     双指针走过的路程以及这三个数之间的关系
     还有一点需要注意的是：
        当头节点为NULL时，它肯定不能循环，甚至不是个链表，直接返回NULL即可。

学习的文章链接：https://programmercarl.com/0142.环形链表II.html#思路

学习的视频链接：https://www.bilibili.com/video/BV1if4y1d7ob/?spm_id_from=333.788&vd_source=c2b246a405f861a2b3c13ab2b1b1eea6

---

学习时长：5h