Day06 | 链表两两交换链表中的结点&&删除链表的倒数第N个结点&&链表相交&&环形链表II

代码随想录 | Day06 | 链表：两两交换链表中的结点&&删除链表的倒数第N个结点&&链表相交&&环形链表II

主要学习内容：

1.双指针操作链表

2.哈希表在链表里的使用（表示唯一行可以存储地址）

24.两两交换链表中的结点

24. 两两交换链表中的节点 - 力扣（LeetCode）

24.两两交换链表中的节点1

注：交换过程有多种不一定非得是图上的

错误写法

错误原因

1.没有用两个结点前面的那个结点作为媒介

2.cur和pre交换完以后没有将两结点前面的结点连接到cur上（事实上也没法连接就是了）

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode * t= new ListNode;
        t->next=head;
        if((!head)||(!head->next))
            return head;
        ListNode *cur=head->next;
        ListNode *pre=head;
        ListNode *tmp;
        while(cur->next != nullptr && cur->next->next != nullptr)
        {
            tmp=cur->next;
            cur->next=pre;
            pre->next=tmp;
            pre=tmp;
            if(tmp)
                cur=tmp->next;
            else
                break;
        }
        return t->next;
    }
};

正确写法

思路：

1.快慢指针分别指向需要做交换的两个结点

2.使用两结点前面的结点作为媒介，能保证和交换完以后的新结点的连接

3.每次要更新快指针cur，慢指针pre，两结点前面的结点t

4.while循环条件保证下两个结点不为空，才能进行交换，如果只剩下1一个那就不做处理，因为不用管结点数量是偶数还是奇数

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode * t= new ListNode;
        t->next=head;
        ListNode *result=t;
        
        while(t->next!=nullptr&&t->next->next!=nullptr)
        {
            //更新快慢指针
            ListNode * cur=t->next->next;
            ListNode * pre=t->next;
            //交换过程 注：交换过程有多种不一定非得是图上的
            pre->next=cur->next;
            cur->next=pre;
            t->next=cur;//上一个写法的错误所在，没有将前一结点与新结点相连接
            //更新结点t
            t=t->next->next;
        }
        return result->next;
    }
};

关键点：

要使用两结点前面的结点作为媒介

19.删除链表的倒数第N个结点

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

（看了力扣的提示才做出来的）

解法：双指针

**思路：**维护两个相差n步的指针，然后同时向前遍历，等快指针到达末尾结点的下一个NULL时，慢指针刚好指向倒数第n个

关键点：

快指针cur初始化为head，慢指针初始化为虚拟头结点，刚开始两者就相差1步，快指针再经过n步完成快指针的任务，然后一起向后移动，当快指针为nullptr时，慢指针刚好是倒数第n个结点的前一个，这样做是为了更好地完成删除操作，不然我们移动到要删除的结点反而有点束手无策

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode * t=new ListNode;
        t->next=head;
        //快慢指针初始化
        ListNode * cur=head;
        ListNode * pre=t;
        while(n--)
            cur=cur->next;
        //快慢指针一起向后移动
        while(cur)
        {
            cur=cur->next;
            pre=pre->next;
        }
        //删除操作
        pre->next=pre->next->next;
        return t->next;
    }
};

面试题02.07.链表相交

面试题 02.07. 链表相交 - 力扣（LeetCode）

解法1：正常想

思路：

首先搞清楚一点，两个相交的点并不是不是结点的val相等而是地址相同

其次思考一个问题，如果两个链表长度相同你会如何做这道题

是不是一起往后遍历然后相同就返回

那现在的任务就是把他俩的长度弄成一样的然后去一起遍历

弄成一样的方法就是求出长度的差值让长度长的链表提前走这么多步，然后二者再一起遍历就相当于是相同长的链表了

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode * t=headA;
        ListNode * tt=headB;
        ListNode * A=headA;
        ListNode * B=headB;
        int sizeA=0,sizeB=0;
        while(t)//求A链表长度
        {
            sizeA++;
            t=t->next;
        }
        while(tt)//求B链表长度
        {
            sizeB++;
            tt=tt->next;
        }
        //让较长的链表提前走的操作
        if(sizeA>sizeB)
        {
            int n=sizeA-sizeB;
            while(n--)
                A=A->next;
        }
        else
        {
            int n=sizeB-sizeA;
            while(n--)
                B=B->next;
        }
        //一起遍历，循环条件A或B都可以，因为此时二者作用相同
        while(A)
            {
                if(A==B)
                    return A;
                A=A->next;
                B=B->next;
            }
        return nullptr;
    }
};

####解法2：哈希表

个人觉得这个比较容易想到

但是要注意是交点是地址值相同而不是结点值相同，第一次做就是这样错了

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode *> visited;
        ListNode *temp = headA;
        //创建哈希表然后将A录入
        while (temp != nullptr) {
            visited.insert(temp);
            temp = temp->next;
        }
        temp = headB;
        //从B里面找，一旦找到就是答案
        while (temp != nullptr) {
            if (visited.count(temp)) {
                return temp;
            }
            temp = temp->next;
        }
        return nullptr;
    }
};

解法3：双指针（个人觉得这个方法太巧妙了背背算了）

假设链表A长度为a，链表B长度为b，相同的长度为c

情况1：a==b

正常遍历到相同节点然后就输出了

情况2：a!=b

那么pA在遍历完a以后会更新为B的头结点，pA走过长度为a

那么pB在遍历完b以后会更新为A的头结点，pB走过长度为b

注意他俩不可能同时遍历完，短的会先遍历完

此时我们计算一下pA到相同节点走过的路程为

A全部和B中到相同节点前的路即为

a+b-c

而你会发现，pB也是

b+a-c

还是一起向后移动的速度还一样

那么如果有相同的点一定会同时到达相同的点

只能说太妙了

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            if(pA == nullptr)
                pA=headB;
            else
                pA=pA->next;
            if(pB == nullptr)
                pB=headA;
            else
                pB=pB->next;
        }
        return pA;
    }
};

//力扣的官方题解
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;
    }
};

142.环形链表II

142. 环形链表 II - 力扣（LeetCode）

解法一：哈希表

思路：

就把遍历过的结点都加入set中，如果出现过就代表是循环的入口，直接返回就是了

循环内可以分为3个情况

1.遍历到nullptr了，则代表没有环

2.有元素重复出现了，代表是环的入口即答案

3.既没有nullptr也没有重复出现，那就加入集合

（看了下环形链表I发现只是个判断有没有环的）

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode *> p;
        ListNode *t=head;
        /*while(true)
        {
            if(t==nullptr)
                return nullptr;
            else if(p.count(t))
                return t;
            else
            {
                p.insert(t);
                t=t->next;
            }
        }*/
        while(t!=nullptr)
        {
            if(p.count(t))
                return t;
            p.insert(t);
            t=t->next;
        }
        return nullptr;
    }
};

解法二：双指针

代码随想录 (programmercarl.com)

此处看该视频会更好理解

关键点

1.快指针两个两个走，慢指针一个一个走，这样不会漏掉快慢指针的相遇点

2.获得没进入环的路径长度等于快慢指针相遇点到环入口的长度这一条件

3.可以去看看视频中画的二维图更好理解（ 13:16 处）

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode * cur=head;
        ListNode * pre=head;
        while(cur!=NULL&&cur->next!=NULL)
        {
            //快慢指针移动
            cur=cur->next->next;
            pre=pre->next;
            if(cur==pre)//两指针项相遇
            {
                //利用进入环的路径长度等于快慢指针相遇点到环入口的长度这一条件进行指针定义
                ListNode * index1=head;
                ListNode * index2=pre;
                //两指针相遇点就是环的入口
                while(index1!=index2)
                {
                    index1=index1->next;
                    index2=index2->next;
                }
                return index1;
            }
        }
        return nullptr;
    }
};