LeetCode 19. 删除链表的倒数第N个节点（双指针和递归的妙用）

2020年7月25日 周六 天气晴 【不悲叹过去，不荒废现在，不惧怕未来】

---

---

题目简介

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

这道题如果没有要求使用一趟扫描实现，还是比较简单的，先遍历一次确定链表的长度N，然后这道题就转化为了删除链表的第 N - n + 1 个结点。那么如何实现一趟扫描就解决这道题呢，有两种解法：快慢指针和递归。

---

解法1. 快慢指针(我去给你探探路~)

快慢指针的思想：开始时慢指针不动，先让快指针移动 n 个位置，然后快慢指针同时移动，之后快指针到达链表尾部的时候，慢指针刚好到达第 N - n 个位置，下一个结点就是需要删除的那个结点~

动图如下，来源于 ”程序员吴师兄“ 的 leetcode 题解，十分感谢。

理解了其中的思想之后，代码也就呼之欲出了：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head) return head;
        int N = 0, idx = 0;
        ListNode* preHead = new ListNode(-1);
        preHead->next = head;
        ListNode *fast = preHead, *slow = preHead;
        
        // 快指针先移动 n 个位置
        for(int i=0;i<n+1;++i){
            fast = fast->next;
        }
      
        // 快慢指针同时移动，快指针到达链表尾部时，慢指针到达第 N - n 个位置
        while(fast){
            slow = slow->next;
            fast = fast->next;
        }
        
        // 删除倒数第 n 个结点
        slow->next = slow->next->next;
        return preHead->next;
    }
};

解法2. 递归(大神，请收下我的膝盖！)

递归的解法是我在这道题的评论区看到的，刚开始没看明白，看懂之后不禁感叹：真是妙蛙种子吃着妙脆角妙进了米奇妙妙屋 妙到家了！

先附上代码：

class Solution {
public:
    int cnt = 0;
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head) return head;
        head->next = removeNthFromEnd(head->next,n);
        cnt++;
        if(cnt==n)  return head->next;
        return head;
    }
};

递归函数在回溯时， cnt 从后往前自加，当 cnt == n 时，即回溯到了倒数第 n 个结点，返回这个结点（head）的下一个结点，相当于删除了此结点。

---

参考文献

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/dong-hua-tu-jie-leetcode-di-19-hao-wen-ti-shan-chu/
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/comments/

本文地址：https://blog.csdn.net/m0_37433111/article/details/107585290