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

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

题目描述

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

示例 1:

输入:head = [1,2,3,4,5], n = 2

输出:[1,2,3,5]


示例 2:


输入:head = [1], n = 1


输出:[]


示例 3:


输入:head = [1,2], n = 1


输出:[1]


提示:


链表中结点的数目为 sz

1 <= sz <= 30

0 <= Node.val <= 100

1 <= n <= sz


进阶:你能尝试使用一趟扫描实现吗?


解题思路

首先是可以用遍历2遍的方法来求结果的。


第一遍遍历得到有多少个节点,就可以得到是正序的第几个节点。


我们不用上面的方法,我们用遍历一边的方法。


双指针的方法——快慢双指针


先让快指针走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* temp=new ListNode;
        temp->next=head;

        ListNode* f,*s;
        f=s=temp;
        //快指针先走
        for(int i=1;i<=n;i++) f=f->next;
        //一起走
        while(f->next)
        {
            f=f->next;
            s=s->next;
        }
        //删除
        ListNode* cur=s->next;
        s->next =cur->next;
        delete cur;
        //删除我们定义的头
        cur=temp->next;
        delete temp;
        //返回结果
        return cur;
    }
};
相关文章
|
27天前
链表的中间结点
链表的中间结点
172 57
05_删除链表的倒数第N个节点
05_删除链表的倒数第N个节点
|
2月前
|
算法
LeetCode第19题删除链表的倒数第 N 个结点
该文章介绍了 LeetCode 第 19 题删除链表的倒数第 N 个结点的解法,通过使用快慢双指针,先将快指针移动 n 步,然后快慢指针一起遍历,直到快指针到达链尾,从而找到倒数第 N 个结点的前一个结点进行删除,同时总结了快慢指针可减少链表遍历次数的特点。
LeetCode第19题删除链表的倒数第 N 个结点
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
42 5
|
3月前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
29 1
【数据结构OJ题】链表中倒数第k个结点
|
2月前
【刷题记录】链表的中间结点
【刷题记录】链表的中间结点
|
3月前
【数据结构OJ题】链表的中间结点
力扣题目——链表的中间结点
21 0
【数据结构OJ题】链表的中间结点
|
4月前
|
算法
19.删除链表的倒数第N个结点
19.删除链表的倒数第N个结点
|
3月前
|
机器学习/深度学习 存储
sdut pta 链表3(优化)-----7-3 sdut-C语言实验-链表的结点插入
sdut pta 链表3(优化)-----7-3 sdut-C语言实验-链表的结点插入
18 0
|
4月前
|
算法 C语言
【数据结构与算法 刷题系列】求链表的中间结点
【数据结构与算法 刷题系列】求链表的中间结点