Saikiran cvn
Saikiran cvn

Reputation: 1

Remove Nth Node From End of List(Leetcode)? - Python

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

Answers (3)

Harshit Paliwal
Harshit Paliwal

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

Yilmaz
Yilmaz

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.

enter image description here

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.

enter image description here

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

Issei Kumagai
Issei Kumagai

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

Related Questions