Linked List: Remove Nth node from End Python

PHOTO EMBED

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/