【LeetCode】19. 删除链表的倒数第 N 个结点-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode】19. 删除链表的倒数第 N 个结点。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1 问题

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
【LeetCode】19. 删除链表的倒数第 N 个结点,LeetCode,Python,leetcode,链表,算法
示例 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]

2 答案

这题直接不会
循环迭代

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head 

        #step1: 获取链表长度
        cur, length = head, 0 
        while cur:
            length += 1
            cur = cur.next 
        
        #step2: 找到倒数第N个节点的前面一个节点
        cur = dummy  # cur 修改时 dummy 也会跟着一起修改，但next操作不会
        for _ in range(length - n):
            cur = cur.next
        
        #step3: 删除节点，并重新连接
        cur.next = cur.next.next
        return dummy.next

3 问题

为什么用head代替dummy不行?
因为可能存在只有一个节点的列表，不能从head开始，要从head的前一个开始文章来源地址https://www.toymoban.com/news/detail-724690.html

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy1 = ListNode(0)
        dummy1.next = head
        length = 0

        dummy = head
        while dummy:
            length += 1
            dummy = dummy.next
        cur = head
        for _ in range(length-n-1):
            cur = cur.next
        cur.next = cur.next.next
        return dummy1.next