链表篇（四）

力扣链表篇四

• 链表篇（四）
• • • 方法一——通过函数计算链表长度后遍历删除：
    • • 解析：
      • 代码
    • 方法二：先反转链表，再遍历删除
    • • 题解概要
      • 代码
    • 方法三——双指针的运用
    • • 题解概况
      • 代码

链表篇（四）

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

方法一——通过函数计算链表长度后遍历删除： 解析：

​ 对于该方法，简单易懂，本题的难点在于是否可以将倒数第n个数删除，因为链表多是以遍历向后 *** 作，所以我们可以在一开始就对原链表进行一次遍历，计算出链表的长度，然后按照正常的遍历结构开始删除。

（从头节点开始对链表进行一次遍历，当遍历到第 L-n+1 个节点时，它就是我们需要删除的节点）

注意点：

• 为了避免出现头节点的特殊情况，我们再次选择虚拟头节点
• 当遍历到第 L-n+1 个节点时，它的下一个节点就是我们需要删除的节点，这样我们只需要修改一次指针，就能完成删除 *** 作

代码

class Solution {
public:
    int getLength(ListNode* head) {
        int length = 0;
        while (head) {
            ++length;
            head = head->next;
        }
        return length;
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy_head = new ListNode(0, head);
        int length = getLength(head);
        ListNode* tmp = dummy_head;
        for (int i = 1; i < length - n + 1; ++i) {
            tmp = tmp->next;
        }
        tmp->next = tmp->next->next;
        ListNode* cur = dummy_head ->next;
        delete dummy_head;
        return cur;
    }
};

方法二：先反转链表，再遍历删除 题解概要

基于链表篇（三）_LuciferPluto的博客-CSDN博客的反转链表题解经验，我们可以继续沿用反转链表的函数 *** 作，然后继续进行以下步骤

1. 反转原链表
2. 遍历删除第n个结点
3. 在返回反转的变链表

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head){
        ListNode *tmp ;// 保存cur的下一个节点
        ListNode *pre = NULL;
        ListNode *cur = head;
        while(cur){
            tmp = cur->next;
            cur->next = pre;//反转指针
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* head_new = reverseList(head);
        ListNode* dummy_head = new ListNode(0, head);
        ListNode* cur = dummy_head;
        cur->next = head_new;
        for(int i = 0; i < n; i++){
            if(i == n - 1){
                cur->next = cur->next->next;
                break;
            }
            else{
                cur = cur -> next;
            }
        }
        return reverseList(dummy_head ->next);
    }
};

方法三——双指针的运用 题解概况

我们利用双指针的快慢指针运用——如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。

删掉slow所指向的节点。

注意点：

• 定义fast指针和slow指针，初始值均为虚拟头结点，如图

• fast先走n+1步，目的是与slow同步，使得同时移动时，slow才能指向删除节点的上一个节点（方便做删除 *** 作）

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy_head = new ListNode(0);
        dummy_head -> next = head;
        ListNode* fast = dummy_head;
        ListNode* slow = dummy_head;
        while(n-- && fast != NULL){
            fast = fast->next;
        }
        fast = fast -> next;
        while(fast!= NULL){
            slow = slow->next;
            fast = fast->next;
        }
        slow -> next = slow -> next ->next;
        return dummy_head -> next;
    }
};