Reputation: 1
Link - https://leetcode.com/problems/remove-nth-node-from-end-of-list/
My approach :
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
h = head
td = h
c = 0
while head.next is not None:
c+=1
print(c,n)
if c>n:
td = td.next
head = head.next
if c + 1 != n:
td.next = td.next.next
return h
It fails in border cases like, [1,2] and n = 2, any way to modify this so that this works for all boarder cases and get accepted? (I know we can solve this using slow and fast pointers)
Upvotes: 0
Views: 1307
Reputation: 1
class Solution:
def removeNthFromEnd(self, head ,n):
temp = dummy = head
count = 0
if head.next == None:
return None
while head.next != None:
count = count + 1
if count > n:
dummy = dummy.next
head = head.next
if count + 1 != n:
dummy.next = dummy.next.next
return temp
Upvotes: 0
Reputation: 49511
We use two pointers technique. "fast_pointer" must be "n" step ahead of "slow_pointer", so when we reach the end of the list, the slow pointer will be the node we are trying to delete.
Let's say we have 5 nodes and we want to delete the 2nd node from the end.
When we reach the end of the list, "slow_pointer" will point to the node that we want to remove. but how are we going to remove it? In order to remove a node from the linked list, its previous node should point to the its next node. In this example, we want to delete the 3rd node, so 2nd node.next should be pointing to the 4th node, since we have no reference of 3rd node, it will be garbage collected, will be removed.
So, we are going to create a dummy node, its value is not important but its next will be pointing to the "head" of the linked list. And our slow pointer will be starting from dummy.
class Solution:
def remove(self,head:ListNode,n:int)->ListNode:
dummy=ListNode(0,head)
slow=dummy
fast=head
while n>0 and fast:
fast=fast.next
n-=1
while fast:
slow=slow.next
fast=fast.next
# now delete it
slow.next=slow.next.next
return dummy.next
class ListNode:
def __init__(self,val,next=None):
self.val=val
self.next=next
Upvotes: 1
Reputation: 685
I have posted an alternative solution in case you were interested.
class Solution:
def removeNthFromEnd(self, head, n):
fast = slow = head
for _ in range(n):
fast = fast.next
if not fast:
return head.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return head
Upvotes: 1