LeetCode偶尔一题 —— 19. 删除链表的倒数第N个节点（链表系列）

Anshiii 发布于2019-08-26 10:21 / 3085人阅读

摘要：题目描述给定一个链表，删除链表的倒数第个节点，并且返回链表的头结点。示例给定一个链表和当删除了倒数第二个节点后，链表变为简单的思路用一个数组保存所有的链表节点，遍历完之后可以知道倒数第个链表节点。

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.  
当删除了倒数第二个节点后，链表变为 1->2->3->5.

简单的思路

用一个数组保存所有的链表节点，遍历完之后可以知道倒数第 n 个链表节点。
时间复杂度 为 O(k)，空间复杂度 为 O(k)，这里 k 为链表长度。

进阶

使用两个指针，快指针先遍历 n 个节点，之后两个指针再一起遍历，等到快指针遍历结束后，慢指针指向的当前节点就是倒数第 n 个节点。
时间复杂度 为 O(k)，空间复杂度 为 O(1)，这里 k 为链表长度。

⚠️注意：为了写代码方便，我们可以在链表头节点前加多一个节点。

示例代码：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    let temp = { next: head }
    temp.next = head
    let p = q = temp
    for (let i = 0; i <= n; i++) {
        p = p.next
    }
    while(p) {
        p = p.next
        q = q.next
    }
    q.next = q.next.next
    return temp.next
};

原题地址: https://leetcode-cn.com/probl...
代码不定时更新，欢迎 star 我的 repo

扫描下方的二维码或搜索「tony老师的前端补习班」关注我的微信公众号，那么就可以第一时间收到我的最新文章。

专线服务混合云 linux链表的安全访问合并链表的c语言学生链表的c语言代码关于链表的c语言代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/106047.html

＜LeetCode天梯＞Day025 删除链表的倒数第N个节点（双指针） | 初级算法 | Pyth

摘要：示例输入输出示例输入输出示例输入输出提示双指针法分析根据题干的要求，我们需要删除倒数第个节点，在返回头结点。只需要找到倒数第个节点，将其删除，再返回。 ?作者简...

andot 2021-11-16 11:45 评论0 收藏0
LeetCode 19：删除链表的倒数第N个节点 Remove Nth Node From End

摘要：给定一个链表，删除链表的倒数第个节点，并且返回链表的头结点。示例给定一个链表和当删除了倒数第二个节点后，链表变为说明给定的保证是有效的。值得注意的的是，指向应当删除的节点并无法删除它，应当指向该删除节点的前一个节点。给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 Given a linked list, remove the n-th node from the ...

周国辉 2019-07-31 11:30 评论0 收藏0
LeetCode 19：删除链表的倒数第N个节点 Remove Nth Node From End

摘要：给定一个链表，删除链表的倒数第个节点，并且返回链表的头结点。示例给定一个链表和当删除了倒数第二个节点后，链表变为说明给定的保证是有效的。值得注意的的是，指向应当删除的节点并无法删除它，应当指向该删除节点的前一个节点。给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 Given a linked list, remove the n-th node from the ...

qiangdada 2019-08-16 18:40 评论0 收藏0
【刷算法】LeetCode.19-删除链表的倒数第N个节点

摘要：题目描述给定一个链表，删除链表的倒数第个节点，并且返回链表的头结点。示例给定一个链表和当删除了倒数第二个节点后，链表变为说明给定的保证是有效的。题目描述给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。示例：给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明：给定的 n 保证是有效...

Binguner 2019-08-23 11:37 评论0 收藏0
Leetcode：刷完31道链表题的一点总结

摘要：既然说到地址空间了就顺带说一下上面环形链表这道题的另一种很的解法吧。介绍完常规操作链表的一些基本知识点后，现在回到快慢指针。前几天第一次在 Segmentfault 发文—JavaScript：十大排序的算法思路和代码实现，发现大家似乎挺喜欢算法的，所以今天再分享一篇前两个星期写的 Leetcode 刷题总结，希望对大家能有所帮助。本文首发于我的blog 前言今天终于...

DevTalking 2019-08-23 17:50 评论0 收藏0