# 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]:
dummy = ListNode(0, head)
left = dummy
right = head #we actually want right to be head + n
#setting right to be head + n
while n > 0 and right:
right = right.next
n -= 1
#this should get left at previous and right at after thanks to dummy node we inserted
while right:
left = left.next
right = right.next
#delete node
left.next = left.next.next
return dummy.next
#bottom solution is what I first came up with and works in leetcode except for if head = [1] and n = 1 which is the case I tried to account for in the second elif statement but it gave me an error saying cannot return [] even though it was fine for the first if statement
#big O: is still O(n) just like 1st scenario
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
if head is None:
return []
elif head.next is None and n == 1:
return []
else:
current = head
counter = 0 #will become length of LL
#to determine length of LL
while current is not None:
counter += 1
current = current.next
#consider adding an edge case here if n > counter
#second pass now knowing length of LL
previous, current = head, head
new_counter = 0
target = counter - n
while new_counter is not target + 1:
if new_counter == (target - 1):
previous = current
if new_counter == target:
after = current.next
previous.next = after
current.next = None
break
current = current.next
new_counter += 1
return head