当前位置：首页 > article >正文

leetcode之hot100---19删除链表的第N个节点（C++）

article 2024/12/26 6:42:35

思路一：获取链表长度

首先获取链表的长度，然后根据链表长度与n的关系找到要删除的节点前驱的位置，

删除节点的方式是，使当前节点的后继变为其后继的后继

但是要注意链表中只有头节点且需要删除的也是头节点的情况

/**
 * 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* p = head;
        int count = 0;
        int len = 0;
        //遍历链表获取其长度
        while(p){
            len++;
            p = p->next;
        }
        
        //创建一个值为0后继为头节点的哨兵节点
        ListNode* sentry = new ListNode(0, head);
        
        //当要删除的节点为头节点且表中只有一个头节点时，
        //如果从头节点开始寻找要删除节点的位置会导致指针找不到位置
        //也就是在执行 p->next = p->next->next代码时会导致错误
        //因此，为了避免出现上述情况，选择从哨兵位置开始遍历
        p = sentry;
        while(count != len - n){
            p = p->next;
            count++;
        }
        p->next = p->next->next;
        ListNode* ans = sentry->next;
        delete(sentry);
        return ans;
    }
};

时间复杂度：O(N)
空间复杂度：O(1)

思路二：双指针

先利用first指针找到第n个位置的节点，然后first指针和second指针同时移动，当first指针遍历到表尾，此时second指针刚好指向倒数第n个位置

/**
 * 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) {
        //创建一个值为0后继为头节点的哨兵节点
        ListNode* sentry = new ListNode(0, head);
        ListNode* first = head;
        ListNode* second = sentry;
        int cnt = 0;
        //利用first找到第n个节点
        while(cnt < n){
            first = first->next;
            cnt++;
        }
        //同时更新first和second位置
        //由于first超second n个位置
        //当first遍历到链表的表尾时，second就恰好在倒数第n个节点
        while(first){
            first = first->next;
            second = second->next;
        }
        //删除倒数第n个节点
        second->next = second->next->next;
        ListNode* ans = sentry->next;
        delete sentry;
        return ans;
    }
};