代码编织梦想

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

原题链接:删除链表的倒数第 N 个结点

个人解法

思路:

倒数第k个数可以换一个角度来看,倒数第k个数就是倒数第k个数与最后一个数的相距为k(这里包括边界的两个数)。那么我们可以平移这一段距离到起点位置。
设置两个指针 i 和 j,其中 i 指向链表的头,j 指向距离 i 为 k 距离的元素。那么当 j 遍历到链表尾部的时候,此时就变为了满足 j 为指向链表尾部元素, i 距离 j 为 k(包括边界)。
那么 i 所指向元素即为倒数第 k 个数。删除这个数即可。
注意:这里为了删除 i 所指向的数,维护 i 左和右两个指针 l 和 r。用于删除结点 i。

时间复杂度: O ( n ) O(n) O(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) {
        if(head->next == nullptr) return nullptr;
        ListNode *H = new ListNode();
        H->next = head;
        if(n == 1) {
            ListNode *p = head;
            while(p->next->next) {
                p = p->next;
            }
            p->next = nullptr;
            return head;
        }
        ListNode *i = head, *j = H, *l = H, *r = i->next;
        for(int i = 0;i < n;i ++) j = j->next;
        while(j->next) {
            l = i;
            i = r;
            r = r->next;
            j = j->next;
        }
        l->next = r;
        return H->next;
    }
};
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Archerrrrr/article/details/128820470

【lc刷题】19 删除链表的倒数第n个节点(链表)_day05_loewi大湿的博客-爱代码爱编程

14/300 删除链表的倒数第N个节点   给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。   示例:   给定一个链表: 1->2->3->4->5, 和 n = 2.

[leetcode-javascript]---19.删除链表的倒数第n个节点_weixin_34216036的博客-爱代码爱编程

题目 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5. 复制代码 说明: 给定的 n 保证是有效的。 思考 这道题要用双指针

19删除链表的倒数第n个结点_ustb_lc的博客-爱代码爱编程

删除链表的倒数第n个结点 题目描述:编写一个程序,找到两个单链表相交的起始节点。没有就返回null。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒

每天一道leetCode题--19--删除链表的倒数第N个节点-爱代码爱编程

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5. 说明: 给定的 n 保证是有效的。 进阶: 你能尝试使用一趟扫描实现吗? /* * @lc app=

LC019-删除链表的倒数第N个节点-爱代码爱编程

19. 删除链表的倒数第N个节点 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5. 方法一:栈 常规思维 算链表长度,然后再找倒数第n个。 栈 先压

刷题-Leetcode-19. 删除链表的倒数第 N 个结点(快慢指针)-爱代码爱编程

19. 删除链表的倒数第 N 个结点 题目链接 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/ 题目描述 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 进阶:你能尝试使用一趟扫描实现吗? 示例 1:

【icyle】Leetcode-cn:19. 删除链表的倒数第 N 个结点-爱代码爱编程

题目 解答1:找位置 思路 先找位置再删除,最简单的方法。 需要的头文件 无 代码 /* * @lc app=leetcode.cn id=19 lang=cpp * * [19] 删除链表的倒数第 N 个结点 */ // @lc code=start /** * Definition for singly-linked list

(leetcode)160. 相交链表 2021/6/4-爱代码爱编程

文章目录 160. 相交链表 javascript 160. 相交链表 javascript 题目: 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。 图示两个链表在节点 c1 开始相交: 题目数据 保证 整个链式结构中不存在环。 注意,函数返回结

LC.19. 删除链表的倒数第 N 个结点-爱代码爱编程

知识点: 寻找链表倒数第n个节点:采用双指针法,先让快指针走 n 步,之后让快、慢指针一起走,当快指针为空时,慢指针所指即为倒数第 n 个节点。删除链表中某一节点的思路:单链表中,一个节点的删除需要借助其前一个节点,这样才能保证删除后链表的完整、连续。但头节点前没有节点,所以与其他节点不同,需要额外处理。若头节点需要删除,只需将 head 指向 head

LeetCode-【双指针】删除链表的倒数第 N 个结点-爱代码爱编程

题目描述 以下截图来自于 VSCode 的 LeetCode 插件: 题目分析 需要注意几点 python不同于C语言,是一种按对象引用传递的语言,详细介绍见:https://robertheaton.com/2014/02/09/pythons-pass-by-object-reference-as-explained-by-philip-k-d

力扣初级算法-18-链表-删除链表的倒数第N个节点-爱代码爱编程

学习目标: 本次学习目标为 力扣初级算法-链表,其中主要的LC如下: 删除链表的倒数第N个节点学习内容: 删除链表的倒数第N个节点 -----(链接) 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 示例1: 输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 示例2: 输入:head

一刷10-链表-19删除链表的倒数第n个节点(m)-爱代码爱编程

题目: 给一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 ---------------- 示例: 输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 输入:head = [1], n = 1 输出:[] 输入:head = [1,2], n = 1 输出:[1] ----------------- 思路

2022.03.15(LC_19_删除链表的倒数第 N 个结点)-爱代码爱编程

 方法一:两趟扫描 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val =

LC 19. 删除链表的倒数第 N 个结点-爱代码爱编程

  class Solution { /** 思路: 快慢指针 快指针先走 n + 1 步, 慢指针再出发, 快指针走到头时, 慢指针刚好到达 倒数第 n 个节点的前一个节点, 删除返回 */ public ListNode removeNthFromEnd(ListNode head,

力扣js lc [19. 删除链表的倒数第 n 个结点] lc [面试题 02.07. 链表相交]_想学好前端的小宝的博客-爱代码爱编程

LC 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 输出:[