LeetCode

Appearance

19. Remove Nth Node From End of List ​

题目 ​

Given the head of a linked list, remove the nth node from the end of the list and return its head.

 

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

 

Constraints:

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

 

Follow up: Could you do this in one pass?

Related Topics
  • 链表
  • 双指针

  • 👍 3122
  • 👎 0

    • 思路 ​

    采用双指针的策略，fast 指针和 slow 指针相差 N 个元素，当 fast 指针指向末尾时，slow 指针的指向要删除的元素

    • 删除可能包含头节点，需要使用 dummy 指针
    • 执行删除操作时，需要找到删除的前一个元素，所以最后的 fast 指针指向最后一个元素，而非末尾空指针，终止条件是（fast.next）
    • N 为 fast 指针先行的步数， 使用 for 进行先行步骤
    • 同时移动 fast 和 slow 元素
    • 删除目标元素即可

    解法 ​

    py
    # leetcode submit region begin(Prohibit modification and deletion)
# 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: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        fast = dummy
        for i in range(n):
            fast = fast.next

        slow = dummy

        while fast.next:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next if slow.next else None

        return dummy.next
        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度 O(N)
    • 空间复杂度 O(1)