LeetCode19删除链表的倒数第N个结点

题目链接

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

题解一

• 双指针：一个“快”，一个“慢”
• 快指针先到达链表末尾
• 具体思路见代码及注释

// Problem: LeetCode 19
// URL: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
// Tags: Linked List Two Pointers Recursion
// Difficulty: Medium

#include <iostream>
using namespace std;

struct ListNode{
    int val;
    ListNode* next;
};

class Solution{
public:
    // 删除链表的倒数第N个结点
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 快慢指针
        ListNode* fast = head, *slow = head;
        // 快指针先移动N+1步，慢指针不移动
        int i = 0;
        while (i <= n && fast != nullptr){
            fast = fast->next;
            i++;
        }
        // 这个if语句和上个while循环中的fast!=nullptr都是为了处理一种特殊情况：
        // 假如链表只有N个元素且要删除倒数第N个元素，则快指针不能移动N+1步，这时应直接删除头结点
        if(i!=n+1){
            // 删除头结点并返回新链表
            head = head->next;
            delete slow;
            return head;
        }
        // 快指针和慢指针一起移动直至快指针为空
        // 因为快指针先移动了n+1步，所以循环结束后慢指针是指向待删除结点前面的那个结点
        while(fast!=nullptr){
            fast = fast->next;
            slow = slow->next;
        }
        // 删除待删除的结点并返回新链表
        fast = slow->next;
        slow->next = fast->next;
        delete fast;
        return head;
    }
};

题解二

• 递归写法，很厉害，我参考了别人的

// Problem: LeetCode 19
// URL: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
// Tags: Linked List Two Pointers Recursion
// Difficulty: Medium

#include <iostream>
using namespace std;

struct ListNode{
    int val;
    ListNode* next;
};

class Solution{
private:
    int index=0;
public:
    // 删除链表的倒数第N个结点
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == nullptr) return nullptr;
        // 递归表达式
        head->next = removeNthFromEnd(head->next, n);
        // 该变量用来标记是倒数第几个结点，这条语句写在了递归表达式之后，这很关键
        index++;
        // 此时head即为待删除结点前边的那个结点
        if(index == n) return head->next;
        return head;
    }
};

---

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!

---