【DS】链表面试热题之倒数节点及其变体

超、凢脫俗 2024-04-03 10:01 84阅读 0赞

##  ##

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

*  
 *   *  一、输出链表中倒数最后k个节点
     *   *  题目描述
         *  思路分析
         *  画图分析
         *  AC代码
     *  二、删除链表的倒数第n个节点
     *   *  题目描述
         *  思路分析
         *  画图分析
         *  AC代码

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

***倒数节点操作核心思路：***

双指针：先不同时出发，再同时出发。  
模板：

while (k  != 0) {
        
        if (fast == null) {
         //链表的长度小于k
            return null;
        }
        fast = fast.next;
        k--;
    }
    while (fast != null) {
        
        fast = fast.next;
        slow = slow.next;
    }

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

### 一、输出链表中倒数最后k个节点 ###

#### 题目描述 ####

1.输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。如果该链表长度小于k，请返回一个长度为 0 的链表。[OJ链接][OJ]

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

1.  本题使用双指针，一个先走k步。然后再一起走，速度均为1
2.  第一个循环条件是k!=0，第二个循环条件是fast!=null

#### 画图分析 ####

![在这里插入图片描述][a36addb3b12d41849b000b263e4abd6c.png_pic_center]

#### AC代码 ####

public ListNode FindKthToTail (ListNode head, int k) {
        
        ListNode fast = head;
        ListNode slow = head;
        while (k  != 0) {
        
            if (fast == null) {
         //链表的长度小于k
                return null;
            }
            fast = fast.next;
            k--;
        }
        while (fast != null) {
        
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

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

#### 题目描述 ####

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针。[OJ链接][OJ 1]

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

1.  这道题是上道题的变体
2.  删除倒数第n个节点的关键是拿到它的前驱节点，这个时候改写上题的函数直接调用
3.  但是这样还不能直接AC，还需要考虑像这样`{1,2},2` 头结点被删的情况，这个时候定义一个虚拟头节点是再好不过了。

#### 画图分析 ####

![在这里插入图片描述][a03b80385ce540f6a96dd5e7921ad7d0.png]

#### AC代码 ####

public ListNode removeNthFromEnd (ListNode head, int n) {
        
        // write code here
        ListNode res=new ListNode(-1);
        res.next=head;
        ListNode node = FindKthPrevToTail(res, n);
        node.next=node.next.next;
        return res.next;
    }
    private ListNode FindKthPrevToTail (ListNode head, int k) {
        
        ListNode fast = head;
        ListNode slow = head;
        while (k != 0) {
        
            if (fast == null) {
         //链表的长度小于k
                return null;
            }
            fast = fast.next;
            k--;
        }
        while (fast.next!= null) {
        
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

[OJ]: https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9?tpId=295&tqId=1377477&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
[a36addb3b12d41849b000b263e4abd6c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/a6552dd6411c4726bee517b9a4f05216.png
[OJ 1]: https://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6?tpId=295&tqId=727&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
[a03b80385ce540f6a96dd5e7921ad7d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/7d596d4a21a8478ea9faa726002f790b.png