19. Remove Nth Node From End of List
Please review the solution and try implementing on your own if you haven’t gotten it.
- 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
- 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