跳转至

19 删除链表的第N个节点

leetcode

解题思路

思路

引入哑节点dummyNode:

  • 防止出现空指针的情况,比如说链表总共有 5 个节点,题目就让你删除倒数第 5 个节点,也就是第一个节点,那按照算法逻辑,应该首先找到倒数第 6 个节点。但第一个节点前面已经没有节点了,这就会出错。
  • 循环结束条件为fast == nullptr,这时指针fast指向nullptr,这是链表多出来的无效节点,导致正数和倒数的索引不对称。而引入哑节点之后,链表形成对称,正数和倒数对应的索引相同。
  • 另外,引入dummyNode之后,从dummyNode或nullptr出发,到达「正数第n个节点」或「倒数第n个节点」所需跳跃次数恰好为n

picture 0

删除倒数第n个节点:

  • 获取倒数第n + 1个节点实现删除
  • 引入dummyNode之后,倒数第n + 1个就是正数第n + 1个,需要跳跃n + 1次

Solution

/**
* 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* dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode* fast = dummyNode, * slow = dummyNode;
        // 获取正数第n + 1个节点
        for(int i = 0; i < n + 1; i++){
            fast = fast->next;
        }
        // 正数第n + 1个就是倒数第n + 1个
        while(fast != nullptr){
            fast = fast->next;
            slow = slow->next;
        }
        // 删除第n个节点
        ListNode* deleteNode = slow->next;
        slow->next = deleteNode->next;
        delete deleteNode;
        return dummyNode->next;
    }
};
/**
* 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 {
private:
    ListNode* findFromEnd(ListNode* head, int n){
        // 创两个指针,初始都指向head
        ListNode* p1 = head, * p2 = head;
        // p2向右移动n步,使其与p1相距n,假设p1对应索引为index,那么p2对应索引为index + n
        for(int i = 0; i < n; i++){
            p2 = p2->next;
        }
        // 同时让两个指针运动,当p2移动到链表末尾的下一个位置(空指针)[index = size],p1刚好为倒数第n个节点[index = size - n]
        while(p2 != nullptr){
            p1 = p1->next;
            p2 = p2->next;
        }
        // p1就是我们求的倒数第n个节点
        return p1;
    }
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // dummyNode:因为可能删除头节点,所以我们需要一个虚拟头节点表示链表的开始
        // 另外,头节点可能为空,返回dummyNode->next避免了判断头节点为空的情况
        ListNode* dummyNode = new ListNode(-1);
        dummyNode->next = head;
        // 删除倒数第n个节点,需要遍历其前一个节点,也就是倒数第n + 1个节点
        ListNode* target = findFromEnd(dummyNode, n + 1);
        target->next = target->next->next;
        return dummyNode->next;
    }
};

复杂度分析

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)