力扣19删除链表的倒数第 N 个结点：思路分析+图文全解+方法总结（快慢指针法&递归法）+深入思考

爱被打了一巴掌 2024-04-24 14:38 2阅读 0赞

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

*  第一部分：题目描述
 *  第二部分：代码实现
 *   *  2.1 快慢指针法
     *  2.2 递归

## 第一部分：题目描述 ##

🏠 链接：[19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）][19. _ N _ - _LeetCode]

⭐ 难度：中等

![image-20230513080722075][]

## 第二部分：代码实现 ##

### 2.1 快慢指针法 ###

> 快慢指针，p1 指向待删节点的上一个，p2 先走 n + 1 步。

步骤：

1.  快慢指针都指向哨兵 sentinel （创建sentinel节点，将 sentinel 的下一个节点设置为头节点 head）。
2.  fast 向后移动 `n+1` 个位置，使得 slow 与 fast 保持了 `n+1` 个距离。
3.  fast 和 slow一起向后移动（移动相同距离），直到 fast 到最后一个节点的下一个节点（ null ）。fast 和 slow 始终保持着 n+1 个位置的距离。要删除的倒数的第 n 个节点，就是 slow 的下一个节点。
4.  删除节点就是将 改变 slow 的下一个节点为 slow 的下下个节点。
5.  返回真正的头节点，就是 sentinel 的下一个节点。

图解分析：

已知链表 1 -> 2 -> 3 -> 4 -> 5，需要删除倒数第 2 个节点（n = 2）

![image-20230514001541285][]

class Solution {
        
        public ListNode removeNthFromEnd(ListNode head, int n) {
        
            // 链表：sentinel -> 1 -> 2 -> 3 -> 4 -> 5
            // n = 2，应当删除节点4
    
            // 哨兵节点，作为伪头节点
            ListNode sentinel = new ListNode(-1, head);
            // 快指针
            ListNode fast = sentinel;
            // 慢指针
            ListNode slow = sentinel;
    
    
            // 先将 快指针 移动到 慢指针 n+1 个位置后
            // 移动后 fast 指向 3，slow 指向 sentinel
            while (n > -1) {
        
                fast = fast.next;
                n--;
            }
    
            // 将快慢指针向后移动，知道 快指针到了最后一个节点的下一个节点 null
            // 此时 慢指针 指向节点的 下一个节点就是待删除的节点 (val = 3)
            while (fast != null) {
        
                slow = slow.next;
                fast = fast.next;
            }
    
            // 将当前慢指针指向节点的下一个节点更改为 待删除节点的下一个节点
            // 那么此时 3 -> 5
            slow.next = slow.next.next;
    
            // 返回真正的头节点
            return sentinel.next;
        }
    }

❓ 为什么要设置一个sentinel

Answer：主要是**考虑待删除的节点正好是头节点 head 的情况**。我们知道在单链表中我们想要删除一个节点需要依靠它的上一个节点，而头节点head没有上一个节点，因此我们暂时给 head 前面加一个伪头节点 sentinel 指向 head。这样就能像其它节点一样通过待删除节点的上一个节点来删除待删除的节点。

### 2.2 递归 ###

思路：写一个递归函数，用来返回下一个节点的倒数序号。

recursion(ListNode p=1, int n=2) {
        
        recursion(ListNode p=2, int n=2) {
        
        	recursion(ListNode p=3, int n=2) {
        
        		recursion(ListNode p=4, int n=2) {
        
        			recursion(ListNode p=5, int n=2) {
        
        				recursion(ListNode p=null, int n=2) {
        
        					return 0; // 最内层序号0
    					}
                        return 1; // 上一次返回值+1
    				}
                    return 2;
    			}
                if(返回值 == n == 2) {
        
                    // 删除 next
                }
                return 3;
    		}
            return 4;
    	}
        return 5;
    }

但上述代码有一个问题，就是若删除的是第一个节点，它没有上一个节点，因此可以加一个哨兵来解决。

class Solution {
        
        public ListNode removeNthFromEnd(ListNode head, int n) {
        
            ListNode sentinel = new ListNode(-1, head);
            recursion(sentinel, n);
            return sentinel.next;
        }
    
        /**
         * @param p 当前节点
         * @param n 需要删除倒数第 n 个节点
         * @return 当前节点为 倒数第几个节点
         */
        private int recursion(ListNode p, int n) {
        
            // 如果无节点了，就返回 0
            if (p == null) {
        
                return 0;
            }
            // nth 代表的是下一个节点的倒数位置
            int nth = recursion(p.next, n);
            // 如果下一个节点是 第 n 个节点，就需要删除下一个节点
            if (nth == n) {
        
                p.next = p.next.next;
            }
            // 当前节点的倒数位置 nth + 1
            return nth + 1;
    
        }
    }

Question：p.next.next 不怕空指针吗？

Answer：

*  p 是待删除节点的上一个节点，如果能递归回到 p，那么 p.next 肯定有值，不会是 null
 *  且题目说明了 n >=1，不会因为 nth == 0 而让 p.next 指向最后的 null

[19. _ N _ - _LeetCode]: https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
[image-20230513080722075]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/4717721e362148ddb71c5b3a433fd52c.png
[image-20230514001541285]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/d72ebbc1f6e44fe7b4d102a5490f2fc5.png