# LeetCode Medium 19. Remove Nth Node From End of List

tags: leetcode

問題

• Explore
• Problems

アイデア

｢後ろからn番目のノードを連結リストから取り除け｣という問題です．

2つのポインタを使います．

解法

• 片方のポインタをnつ先に進め，このポインタが末尾にたどり着いたときのもう片方のポインタが答えです．

計算量

リストの大きさを$N$とする．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(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:
        dummy = ListNode(0)
        dummy.next = head
        fast = slow = dummy
        for _ in range(n):
            fast = fast.next
        while fast and fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next