Leetcode4刷题day4|第二章链表2| 24. 两两交换链表中的节点|19.删除链表的倒数第N个节点 |02.07. 链表相交 |142.环形链表II【含步骤拆分图】

待我称王封你为后i 2024-03-31 09:08 11阅读 0赞

##  ##

#### 文章目录 ####

*  
 *   *  前言
     *  一、两两交换链表中的节点
     *   *  思路分析
         *  注意事项
         *  AC代码
         *  拓展：递归版本
     *  二、删除链表的倒数第N个节点
     *   *  思路分析
         *  注意事项
         *  AC代码
     *  三、链表相交
     *   *  思路分析
         *  AC代码
     *  四、环形链表II
     *   *  思路分析
         *  注意事项
         *  AC代码
     *  五、总结

### 前言 ###

> 这是之前写过的博文，大家感兴趣可以看看
> 
> [环形链表及其变体][Link 1]
> 
> [倒数节点及其变体][Link 2]

### 一、两两交换链表中的节点 ###

[题目链接][Link 3]

#### 思路分析 ####

核心思路：双指针

1.  使用虚拟头节点和原链表链上
2.  定义循环变量cur，初始值为ret，定义node1和node2，初始值分别为第第一组需要交换的节点位置
3.  修改三个节点之间的指向，达到“交换节点的位置”的目的
4.  先将上一组的node2和这一组的node2连接==>再将这一组的node1和下一组的node1连接==>再将这一组的node2和node1连接起来。【以不适用tmp变量为例】
5.  重复上述操作，直至node2为空或者均为空（分别对应奇数节点和偶数节点情况）

#### 注意事项 ####

1.  交换两个节点：不是交换对应的val值，是要我们必须修改指针的指向！！！
2.  循环条件的设置【设置不当造成引用为空/死循环问题】：必须是成对的节点对应的val值才能够进行交换。换而言之，如果链表节点个数是偶数，两个同时走到空没法交换；链表节点个数为奇数，其中一个为空，还是没法交换。因此设置为`cur.next!=null&&cur.nexnt.next!=null;`,其中cur是前一个节点。
3.  这里边修改node2节点指向的时机决定了我们到底需不需要临时变量来记录node2后边的值。我们理解清楚这个临时变量起的作用——害怕后边的节点找不到，也就知道到底用不用了。下边是两种思路改变指向的思路的图示。
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3I7WqhdG-1668912354623)(F:\\typora插图\\image-20221120092818282.png)\]][img-3I7WqhdG-1668912354623_F_typora_image-20221120092818282.png]

![				\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-m5fX1SW7-1668912354624)(F:\\typora插图\\image-20221120093403178.png)\]][img-m5fX1SW7-1668912354624_F_typora_image-20221120093403178.png]

#### AC代码 ####

//写法一：不适用临时变量记录
    class Solution {
        
        public ListNode swapPairs(ListNode head) {
        
            ListNode ret=new ListNode(-1);
            ret.next=head;
            ListNode cur=ret;
            while(cur.next!=null&&cur.next.next!=null){
        
                ListNode node1=cur.next;
                ListNode node2=cur.next.next;
                cur.next=node2;
                node1.next=node2.next;
                node2.next=node1;
                cur=node1;
            }
            return ret.next;
        }
    }

//写法二：使用临时变量记录
    class Solution {
        
        public ListNode swapPairs(ListNode head) {
        
            ListNode ret=new ListNode(-1);
            ret.next=head;
            ListNode cur=ret;
            while(cur.next!=null&&cur.next.next!=null){
        
                ListNode node1=cur.next;
                ListNode node2=cur.next.next;
                cur.next=node2;
                ListNode tmp=node2.next;
                node2.next=node1;
                node1.next=tmp;
                cur=node1;
            }
            return ret.next;
        }
    }

#### 拓展：递归版本 ####

class Solution {
        
        public ListNode swapPairs(ListNode head) {
        
    		if(head==null||head.next==null){
        
                return head;
            }
            //head是原链表的第一个节点
            ListNode newHead=head.next;//原链表的第二个节点
            
            head.next=swapPairs(newHead.next);//子递归表示让剩余的节点两两交换
            //head.next=……表示让交换后的第二个节点和后边的连接
            
            //表示让交换后的第一个节点和后边的连接
            newHead.next=head;
    		
            return newHead;
        }
    }

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

[题目链接][Link 4]

#### 思路分析 ####

核心思路：快慢指针/双指针

1.  定义虚拟节点，连接到原链表上
2.  定义快慢指针,初始值均为ret。快指针走n步，由于这里n已经指定范围，一定是合法的，所以没必要再判断fast是不是空
3.  慢指针和快指针每次走一步，快指针走到最后一个节点，停止
4.  慢指针的next指向它next.next
5.  返回头结点

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AFl879OJ-1668912354625)(F:\\typora插图\\image-20221120101056130.png)\]][img-AFl879OJ-1668912354625_F_typora_image-20221120101056130.png]

#### 注意事项 ####

1.  怎么找到第倒数第n个节点：快指针走n步，慢指针和快指针再同时走，快指针的next为空,此时慢指针指向倒数第n个节点的前一个位置，使用`slow.next=slow.next.next`；
2.  删除节点操作的实现，`cur.next=cur.next.next`;
3.  我认为，本题使用虚拟头结点的好处是方便这个测试用例的通过
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Tk2elrT1-1668912354626)(F:\\typora插图\\image-20221120100552950.png)\]][img-Tk2elrT1-1668912354626_F_typora_image-20221120100552950.png]
    
    假设我们不使用虚拟头，那么此时直接返回head就是错的！！！

#### AC代码 ####

class Solution {
        
        public ListNode removeNthFromEnd(ListNode head, int n) {
        
            ListNode ret=new ListNode(-1);
            ret.next=head;
            ListNode fast=ret;
            ListNode slow=ret;
            while(n--!=0){
        
                fast=fast.next;
            }
            while(fast.next!=null){
        
                slow=slow.next;
                fast=fast.next;
            }
            slow.next=slow.next.next;
            return ret.next;
        }
    }

### 三、链表相交 ###

[题目链接][Link 5]

#### 思路分析 ####

1.  求出链表A、B长度，这两个链表一定满足一个长度大于另一个的
2.  我们可以定义两个引用，一个逻辑上始终指向比较长的链表，另外一个逻辑上始终指向比较短的链表。一开始的时候我们不知道，可以先进行赋值，然后再比较长度，如果不满足就交换过来【假设，先赋上再说】
3.  消除长度差，让长的先走长度差步
4.  再一起走，每走一步，看谁不是相遇了，相遇了就相交了，返回第一个交点
5.  为空了，就是没有交点

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wsCXTd7u-1668912354626)(F:\\typora插图\\image-20221120103053634.png)\]][img-wsCXTd7u-1668912354626_F_typora_image-20221120103053634.png]

#### AC代码 ####

public class Solution {
        
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
            int lenA=0;
            int lenB=0;
            ListNode ps=headA;
            ListNode pl=headB;
            while(ps!=null){
        
                lenA++;
                ps=ps.next;
            }
            while(pl!=null){
        
                lenB++;
                pl=pl.next;
            }
            if(lenA>lenB){
        
                ps=headB;
                pl=headA;
            }else{
        
                //一定记得赋对对象了也要把引用拉回起始位置
                ps=headA;
                pl=headB;
            }
            //消除长度差
            int cnt=Math.abs(lenA-lenB);
            while(cnt--!=0){
        
                pl=pl.next;
            }
            while(ps!=null&&pl!=null){
        
                if(pl==ps){
        
                    return pl;
                }
                ps=ps.next;
                pl=pl.next;
            }
            return null;
        }
    }

### 四、环形链表II ###

[题目链接][Link 6]

#### 思路分析 ####

核心思路：快慢指针/双指针

1.  判断有没有环——快慢指针法
2.  如果有环，找到第一个节点
    
    可见这篇博文

#### 注意事项 ####

1.  当第一个循环终止后，无环的判断条件
2.  当第一个循环终止后，slow需要拉回起点（头结点/虚拟头结点处）
3.  slow返回的值即为结果

关键点：

1.  公式的推导（起点—》入口与相遇点----》入口之间的关系）
2.  循环条件的判断
3.  slow的处理

#### AC代码 ####

这个带头不带头均可，可以参考如下代码

//不带头——注意无环的判断条件
    public class Solution {
        
        public ListNode detectCycle(ListNode head) {
        
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null){
        
                fast=fast.next.next;
                slow=slow.next;
                if(fast==slow){
        
                    break;
                }
            }
            if(fast==null||fast.next==null){
        
                return null;
            }
            slow=head;
            while(slow!=fast){
        
                fast=fast.next;
                slow=slow.next;
            }
            return slow;
        }
    }

//带头——注意，此时slow要拉回虚拟头节点处，
    public class Solution {
        
        public ListNode detectCycle(ListNode head) {
        
           ListNode ret=new ListNode(-1);
           ret.next=head;
           ListNode fast=ret;
           ListNode slow=ret;
           while(fast!=null&&fast.next!=null){
        
               fast=fast.next.next;
               slow=slow.next;
               if(fast==slow){
        
                   break;
               }
           }
            if(fast==null||fast.next==null){
        
                return null;
            }
            slow=ret;
            while(slow!=fast){
        
                slow=slow.next;
                fast=fast.next;
            }
            return slow;
        }
    }

### 五、总结 ###

1.  解题思路：双指针/快慢指针
    
    有速度差的、有先走再一块走等等
2.  交换或者删除时，注意改变指向的顺序，不然很容易丢失节点
3.  插入节点时，优先绑定后边的节点。

[Link 1]: http://t.csdn.cn/kCTSL
[Link 2]: http://t.csdn.cn/NLe4h
[Link 3]: https://leetcode.cn/problems/swap-nodes-in-pairs/
[img-3I7WqhdG-1668912354623_F_typora_image-20221120092818282.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/2bb31b2e4f3643a48fb9a1eecf6a62c0.png
[img-m5fX1SW7-1668912354624_F_typora_image-20221120093403178.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/2840cb2f672247e6b1f478f45b49d0fd.png
[Link 4]: https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
[img-AFl879OJ-1668912354625_F_typora_image-20221120101056130.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/07e54c72b5d4498787ef00e8a4d72b8f.png
[img-Tk2elrT1-1668912354626_F_typora_image-20221120100552950.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/25b94b95741247c79baf8cc43b15f067.png
[Link 5]: https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
[img-wsCXTd7u-1668912354626_F_typora_image-20221120103053634.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/db36f15787bf4040a8e79b1761d84cc8.png
[Link 6]: https://leetcode.cn/problems/linked-list-cycle-ii/