NeetCodeのSolutionを書いていく

#

Remove Nth Node From End of List

#

問題

#

リンクリストの先頭であるhead及び整数nが与えられる。 末尾からn番目のノード削除しリストの先頭を返しなさい。

制約

#

ノード数をszとする時

• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

計算量；O(N) メモリ：O(1) Nはノードの数

例

#

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

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

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

メモ

#

計算量をO(N)でメモリをO(1)という制約内でやる必要がある。 一度最後までスキャンして数え、lenを取得。 len - n 番目を削除(リンクを切る)すればよいのでは？ 2回ループするので正しくはO(2N)でO(N)になる。 lenを保持するだけなのでメモリもO(1)。 しかしこれだと単純すぎるので何か罠がありそう。

しかしヒントを見るとこれでいいっぽい。 あるいは、1パスでやるには、nの間を開けたポインタp1,p2を準備して、p2が最後に到達した時のp1を削除するという方法も紹介されていた。

from typing import Optional


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]:
        # 長さを取得
        len = 1
        node = head
        while node and node.next:
            len += 1
            node = node.next

        # ターゲット番号を算出
        t = len - n

        if t == 0 and head:
            return head.next

        # ターゲットを削除
        node = head
        count = 0
        while node and node.next:
            count += 1
            if count == t:
                node.next = node.next.next
            node = None if not node.next else node.next

        return head