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: []
Idea:
- Two pointers.
- Second pointer starts from
nthposition. - Run while second pointer exist.
# 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, n: int):
p1 = head
p2 = head
for _ in range(n):
p2 = p2.next # fast
if not p2:
return head.next # in case: head=[1], n=1 -> return []
while p2.next:
p1 = p1.next
p2 = p2.next
p1.next = p1.next.next
return head
# 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]:
if not head.next:
return None
nodes = {}
cur = head
i = 0
while cur:
nodes[i] = cur
cur = cur.next
i += 1
if i - n == 0:
return head.next
cur = nodes[i - n - 1]
if cur.next:
cur.next = cur.next.next
return head
