leetcodeday19 –删除链表的倒数第 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

一般方法:两次for循环

第一次计算长度,第二次重构链表

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        def getLength(head: ListNode) -> int:
            length = 0
            while head:
                length += 1
                head = head.next
            return length
        
        dummy = ListNode(0, head)
        length = getLength(head)
        cur = dummy
        for i in range(1, length - n + 1):
            cur = cur.next
        cur.next = cur.next.next
        return dummy.next

改进版:

双指针

思路与算法

我们也可以在不预处理出链表的长度,以及使用常数空间的前提下解决本题。由于我们需要找到倒数第n 个节点,因此我们可以使用两个指针first 和 second 同时对链表进行遍历,并且 first 比second 超前 n个节点。当first 遍历到链表的末尾时,second 就恰好处于倒数第 n 个节点。

具体地,初始时 first 和 second 均指向头节点。我们首先使用 first 对链表进行遍历,遍历的次数为 n。此时,first 和 second 之间间隔了 n−1 个节点,即 first 比second 超前了 n个节点。

在这之后,我们同时使用 first 和second 对链表进行遍历。当 first 遍历到链表的末尾(即 first 为空指针)时,second 恰好指向倒数第 n 个节点。

根据方法一和方法二,如果我们能够得到的是倒数第 n 个节点的前驱节点而不是倒数第 n 个节点的话,删除操作会更加方便。因此我们可以考虑在初始时将 second 指向哑节点,其余的操作步骤不变。这样一来,当first 遍历到链表的末尾时,second 的下一个节点就是我们需要删除的节点。

# @lc code=start
# 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:
        dummy = ListNode(0, head)
        first = head
        second = dummy
        for i in range(n):
            first = first.next

        while first:
            first = first.next
            second = second.next
        
        second.next = second.next.next
        return dummy.next

复杂度分析

  • 时间复杂度:O(L),其中 L 是链表的长度。
  • 空间复杂度: O(1)。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注