专栏首页木又AI帮打卡群2刷题总结1006—— 删除链表的倒数第N个节点

打卡群2刷题总结1006—— 删除链表的倒数第N个节点


leetcode第19题:删除链表的倒数第N个节点

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/


【题目】

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

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

说明:
给定的 n 保证是有效的。

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

【思路】

解法一:遍历链表,得到链表长度N。那么删除倒数第n个节点,即为删除第N - n个节点。找到第N - n -1个节点,记为p,q = p.next, p.next=p.next.next, del p(记得清除内存)。

唯一的问题是:如何删除第1个元素,需要单独判断?可以不用这么麻烦:增加一个无意义的头结点,所有的删除逻辑都变成一致的了!

解法二:使用两个指针first和second遍历链表,首先,first指针前进n步,second指针不变;紧接着,first指针和second指针同时前进,直到first.next为None。此时,second指针指向的是倒数第n+1个节点,second.next = second.next.next同时删除无用内存即可。(删除第1个元素的代码逻辑与其它元素的不一样,解决方法参考解法一的说明。)

【代码】

python版本

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # 增加空的头结点,使得逻辑一致
        node = ListNode(val=0, next=head)
        head = node
        
        # 找到第n-1个节点
        count = 0
        p = head
        while count < n:
            count += 1
            p = p.next
        
        # 找到倒数第n+1个节点
        q = head
        while p.next:
            p = p.next
            q = q.next
        
        # 删除倒数第n个节点
        r = q.next
        q.next = q.next.next
        del r
        return head.next

【相似题目】

82. 删除排序链表中的重复元素 II

解题思路:先得到重复的元素值,再根据值删除节点。

83. 删除排序链表中的重复元素

解题思路:p.val = p.next.val,则删除p.next。

203. 移除链表元素

解题思路:p.next.val == target,则删除p.next。

237. 删除链表中的节点

解题思路:p.next == node,则删除p.next

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打卡群刷题总结0625——删除链表的倒数第N个节点

    链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list

    木又AI帮
  • leecode刷题(21)-- 删除链表的倒数第N个节点

    这道题我们可以采用双指针法来解答。定义两个指针 left 和 right, 都让其指向链表的头节点。先让 right 指针向后移动 n 步,然后 left 指针...

    希希里之海
  • 【leetcode刷题】T99-删除链表的倒数第N个节点

    使用两个指针node1和node2,两者相距n个节点。这样,当node2为链表尾部时,删除node1->next即可。注意链表长度等于n这种特殊情况!!

    木又AI帮
  • 【leetcode刷题】20T13-删除链表的倒数第N个节点

    https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

    木又AI帮
  • Leetcode打卡 | No.19 删除链表的倒数第N个节点

    之前我们说过 C 和 C++ 中的指针是个好东西 ,在解决这类问题很是方便 。然而 python 是没有这个概念的 ,包括链表也是模拟链表的相关操作 。刷题到这...

    小小詹同学
  • 删除链表的倒数第N个节点

    宇宙之一粟
  • ​LeetCode刷题实战19:删除链表的倒数第N个节点

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • LeetCode - 删除链表的倒数第N个节点

    LeetCode第19题,中等难度,很经典的一道链表相关的题目。一个多月以前做的,当时一看就知道怎么写,结果代码总是差了点...

    晓痴
  • 19 删除链表的倒数第N个节点

    很自然的是我只能通过头节点head多次的next,找到要被删除的节点,但我们获取的定位是倒数第几个。直观的就是我们通过总长度减去倒数就是我们的next次数

    木瓜煲鸡脚
  • 19. 删除链表的倒数第N个节点

    设置两个指针变量,中间隔N-1个元素,当后面的指针遍历完所有元素指向nil时,前面的指针就指向了想要删除的元素

    Michel_Rolle
  • 19. 删除链表的倒数第N个节点

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-...

    lucifer210
  • LeetCode题解—删除链表倒数第n个结点

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

    码上积木
  • 删除链表的倒数第N个结点(leetcode19)

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

    Vincent-yuan
  • 19. 删除链表的倒数第 N 个结点

    CaesarChang张旭
  • 019. 删除链表的倒数第N个节点 | Leetcode题解

    这里我们可以使用双指针算法,不妨设为指针 A 和 指针 B。指针 A 先移动 n 次, 指针 B 再开始移动。当 A 到达 null 的时候, 指针 B 的位置...

    苏南
  • Swift 删除链表的倒数第N个节点 - LeetCode

    构建双指针first与sec,first先走n步,然后一同运动,当first指向表尾,sec指向的next即是倒数第N个节点,删除即可(next指向next的n...

    韦弦zhy
  • LeetCode 19. 删除链表的倒数第N个节点

    freesan44
  • 动图:删除链表的倒数第 N 个结点

    在链表中要删除某个节点 nodeB,必须先找到 nodeB 的前一节点 nodeA ,再将 nodeA 指向 nodeB 的下一节点 nodeC ,从而实现节点...

    程序员小熊
  • 动图:删除链表的倒数第 N 个结点

    在链表中要删除某个节点 nodeB,必须先找到 该节点的前一节点 nodeA ,再将 nodeA 指向 nodeB 的下一节点 nodeC ,从而实现节点 no...

    程序员小熊

扫码关注云+社区

领取腾讯云代金券