Linked List: Remove Nth node from End Python
Fri Aug 12 2022 20:01:25 GMT+0000 (Coordinated Universal Time)
Saved by
@bryantirawan
#python
#linked
#list
#two
#pointer
#dummy
#node
# 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
content_copyCOPY
https://ibb.co/tJ92TkG: visualization of how dummy node needs to be inserted to get left and right pointer to work.
You need left and right to be separated by n
https://leetcode.com/problems/remove-nth-node-from-end-of-list/submissions/
Comments