NeetCode 150 [Linked List] medium: Remove Nth Node From End of List

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