Day 4 LeetCode

Day 4 Task:

Solutions:

1. Approach 1

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        '''
        19. Remove Nth Node From End of List: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

        1. Get the total length of the LL by traversing till end.
        2. Subtract n from total length to find position of node to be removed.
        3. Traverse till the node right before that position.
        4. Point that node to it's .next.next!
        '''
        list_length = 0
        temp = head
        while(temp):
            temp = temp.next
            list_length += 1
        loc = list_length - n
        if(loc == 0):
            head = head.next
            return head
        temp = head
        while(loc>1):
            temp = temp.next
            loc -=1
        temp.next = temp.next.next
        return head

1. Floyd’s Cycle Algorithm:
→ A way of detecting loops withing linked list, but it can be applied to solve the problem at hand.
→ Understanding the algorithm: https://www.youtube.com/watch?v=MFOAbpfrJ8g
 

'''
#1 We have two pointers, slow and fast initialized to the top of the linked list. 
Since we need to remove nth (ex, n=2) node from the list, we keep fast n steps ahead. 
#2 Once fast is n steps ahead, we first check if fast exists, if it does, we keep moving 
both fast and slow till fast.next doesn't exist.
#3 When fast.next is null, that is fast is right before the end of the linked list 
and slow is n steps behind (right before the node to be deleted), we change the link of 
slow to the next(deleted) to next node. 
#4 Fast is actually null, there is no node to be deleted -> 
i.e: 3 nodes, n=4 -> deleted first.
'''
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        
        slow = head
        fast = head
        for i in range(0,n): #1
            fast = fast.next
        
        if(fast): #2
            while(fast.next):
                slow = slow.next
                fast = fast.next
            slow.next = slow.next.next #3
        else: 
            head = head.next #4
        
        return head

Github Link: