【DS】链表面试热题之反转链表及其变体

冷不防 2024-04-03 10:00 163阅读 0赞

##  ##

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

*  
 *   *  一、反转链表
     *   *  题目要求
         *  思路分析
         *  几点注意：
         *  图示分析：
         *  AC代码
     *  二、反转指定区间
     *   *  题目要求
         *  思路分析：
         *  几点注意：
         *  图示分析
         *  AC代码
     *  三、链表中的节点每k个一组翻转
     *   *  题目要求
         *  思路分析
         *  几点注意
         *  图示分析
         *  AC代码

--------------------

***反转链表核心思路：***

**三指针**：pre、cur、curNext，循环条件cur!=null

**模板**：

ListNode pre=null;
    while(cur!=null){
        
        ListNode curNext=cur.next;
        cur.next=pre;
        pre=cur;
        cur=curNext;
    }

--------------------

### 一、反转链表 ###

#### 题目要求 ####

1.给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。[OJ链接][OJ]

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

1.  链表反转是改变原来的指向，不是new新节点重新链接。
2.  空间复杂度要求O（N），说明只能遍历有限趟，但是面试一般要求我们遍历遍数越少越好。
3.  反转之后，原来的头结点的后继节点变成空，其他的都是原来的前驱节点变成自己的后继节点，原来的尾结点也不需要特殊考虑，连接到前边的节点，直接返回即可。
4.  由此说明，我们需要单独处理头结点，统一处理中间节点和尾结点。
5.  可以发现，原来的头结点直接使用也可以，但同时还需要“前驱节点”【记录更改后链表的前驱】，和一个遍历的节点【初始值为head.next】

#### 几点注意： ####

1.  注意原链表为空的情况
2.  注意只有一个节点的情况
3.  注意cur到底什么时候停止遍历

#### 图示分析： ####

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

#### AC代码 ####

public ListNode ReverseList(ListNode head) {
        
            if (head == null) {
        
                return null;
            }
            if (head.next == null) {
         //只有一个节点，本身就是答案
                return head;
            }
            ListNode cur = head.next;
            head.next = null;
            while (cur != null) {
        
                ListNode curNext = cur.next;
                cur.next = head;
                head = cur;
                cur = curNext;
            }
            return head;
        }

### 二、反转指定区间 ###

#### 题目要求 ####

2.将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 O(1)。[OJ链接][OJ 1]

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

1.  本题其实就是反转链表的变体
2.  重点是：找到需要翻转的区间
3.  这道题需要4个指针，一个是虚拟头res,一个是起始位置的前一个指针pre，起始指针head，head的后一个指针headNext。
4.  pre和head在找到后都不需要在移动，原因是pre只需要指向区间的最后一个指针即可，start只需要指向区间外的第一个指针，所以都不需要移动  
    所以只需要移动headNext指针，那么headNext指针怎么移动的，用head指针的next记录headNext指针的下一个位置

#### 几点注意： ####

1.  下标：注意下标是怎么标的，是从0开始的还是从1开始的，这决定了我们写for循环的次数
2.  m和n的范围：这里的m和n的范围都在0-size内，即使不在范围内，我们只需要在每个for的判断条件上与上一个i<=size（）。
3.  循环次数：循环到底是m和n-m+1次还是m-1和n-m次，画图举个例子就知道是后边的一组
4.  **改变指向和位置后，画图的时候一定别忘了三个引用跟着走，他们的值是节点所在的地址，不是链表中的相对位置，千万千万记得！！**

#### 图示分析 ####

【此图第三个图中的第四个节点值应为2】  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-s5fEimXS-1665129079243)(F:\\typora插图\\image-20221007153842452.png)\]][img-s5fEimXS-1665129079243_F_typora_image-20221007153842452.png]

#### AC代码 ####

public ListNode reverseBetween (ListNode head, int m, int n) {
        
        if (m == n) {
        
            return head;
        }
        // write code here
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode pre = res;
        for (int i = 1; i < m; i++) {
        
            pre = pre.next;
        }
        head = pre.next;//此时已经不是真正的头了，只是一个用来遍历的节点
        //m-n翻转
        for (int i = m; i < n; i++) {
        
            ListNode headNext = head.next;
            head.next = headNext.next;
            headNext.next = pre.next;
            pre.next = headNext;
        }
        return res.next;
    
    }

### 三、链表中的节点每k个一组翻转 ###

#### 题目要求 ####

3.将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表  
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样  
你不能更改节点中的值，只能更改节点本身。[OJ 链接][OJ 2]

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

1.  定义一个新头，每次拿到每组最后的位置，然后一直链接
2.  最后返回新头

#### 几点注意 ####

1.  tail的位置不在反转的区间，他相当于第一题中的循环条件中cur!=null中null的位置
2.  子方法中pre在循环外创建，一开始置空，循环内改变值，循环结束后代表的是新的头的位置
3.  每次子方法之后返回的值都是一个单独的值，需要做链接处理

#### 图示分析 ####

由于这里反转的逻辑同前边是一样的，所以我这里主要演示的是主类里边的逻辑。

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

#### AC代码 ####

public ListNode reverseKGroup(ListNode head, int k) {
        
        if(head==null||head.next==null){
        
            return head;
        }
        ListNode tail=head;
        for (int i = 0; i < k; i++) {
        
            if(tail==null){
        
                return head;//如果剩余的小于k个，不需要返回，直接返回原来的节点
            }
            tail=tail.next;
        }
        ListNode newHead=reverseBetween(head,tail);
        head.next=reverseKGroup(tail,k);
        return newHead;
    }
    private ListNode reverseBetween(ListNode head,ListNode tail){
        
        ListNode pre=null;
        while(head!=tail){
        
            ListNode headNext=head.next;
            head.next=pre;
            pre=head;
            head=headNext;
        }
        return pre;
    }

[OJ]: https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=295&tqId=23286&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
[img-oPCxnrsq-1665129079241_F_typora_image-20221007120204748.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/94fd15c9b93942ab9d626897113a1ac1.png
[OJ 1]: https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=295&tqId=654&ru=%2Fpractice%2F75e878df47f24fdc9dc3e400ec6058ca&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj
[img-s5fEimXS-1665129079243_F_typora_image-20221007153842452.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/346805fed2544a459910332d583a0e81.png
[OJ 2]: https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj
[img-QUKilyWF-1665129079244_F_typora_image-20221007141348300.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/7277f55f55b44ddf81e9f5e0b294bf7b.png