Remove Nth Node From End of List
Given the head of a linked list, remove the n<sup>th</sup> 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 <= 300 <= Node.val <= 1001 <= n <= sz
Follow up: Could you do this in one pass?
アプローチ
思考
- nth ノードを削除する
- linked list の長さを求める
- 無駄な巡回を防ぐために、nth を length で剰余演算を行う
- nth のひとつ前のノードまで移動する（for loop）
- cur.next.next にして、nth を飛ばす（削除する）
- head を返す
実装
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
length = 1
cur = head
while cur.next:
length += 1
cur = cur.next
if length == 1:
return None
nth = n % length
cur = head
for _ in range(length - nth - 1):
cur = cur.next
if cur.next.next:
cur.next = cur.next.next
else:
cur.next = None
return headTime Space
注意点
n % lengthにより、n == lengthのとき0になってしまう- 末尾からリストの長さ番目、つまり先頭ノードを正しく指定できなくなる
- 先頭ノードを削除する処理がない
- 先頭には直前のノードがないため、
return head.nextなどの別処理が必要である
- 先頭には直前のノードがないため、
if cur.next.nextの分岐は不要であるcur.next = cur.next.nextだけで、途中のノードと末尾ノードの両方を削除できる