Problem Description
Given the head of a linked list, remove the n-th 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,2], n = 1 - Output:
[1]
My Idea
The idea here is to use two pointer s and f. First we move f n+1 steps ahead of s, so that there is a n-node gap between s and f. Then we move them together 1 step at a time. When f reaches the end, s is at the node before the one to be removed (at the n+1 -th node). res is needed to handle the case of deleting the first element. We get a time complexity of O(n).
My solution
from typing import Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Time Complexity: O(n)
def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
res = ListNode(0,head)
s = res
f = res
for _ in range(n+1):
if f:
f=f.next
while f:
s=s.next
f=f.next
s.next=s.next.next
return res.next