Leetcode accepted

PriyankaKhire · PriyankaKhire · commit 9effae35d7bc · 2021-08-21T22:58:08.000-07:00
diff --git a/Blind 75/Programs/Remove Nth Node From End of List.py b/Blind 75/Programs/Remove Nth Node From End of List.py
@@ -0,0 +1,40 @@
+# Remove Nth Node From End of List
+# https://leetcode.com/problems/remove-nth-node-from-end-of-list/
+
+# Definition for singly-linked list.
+# class ListNode(object):
+#     def __init__(self, val=0, next=None):
+#         self.val = val
+#         self.next = next
+class Solution(object):
+    def removeNthFromEnd(self, head, n):
+        # we assign fast pointer rabbit to head
+        rabbit = head
+        # since head node is counted as 1, we stop when n = 1
+        while(n > 1):
+            # we want to advance rabbit to n nodes
+            rabbit = rabbit.next
+            n = n-1
+        # we assign slow pointer tortoise to head
+        tortoise = head
+        # we also need previous pointer to concatinate the singly linked list
+        prevPtr = head
+        # move both rabbit and tortoise unitl rabbit reaches the end
+        while(rabbit.next):
+            prevPtr = tortoise
+            rabbit = rabbit.next
+            tortoise = tortoise.next
+        # now tortoise is at the n th to last node.
+        # if we have to remove head, just advance the head to it's next value, even if that value is null.
+        if (tortoise == head):
+            head = head.next
+        else:
+            # we remove tortoise with help of prev pointer
+            prevPtr.next = tortoise.next
+        return head
+        """
+        :type head: ListNode
+        :type n: int
+        :rtype: ListNode
+        """
+        
diff --git a/Blind 75/README.md b/Blind 75/README.md
@@ -180,7 +180,10 @@
         <p><b>Approach</b>: Use heap sort to merge k lists.
         </p>
       </li>
-      <li>Remove Nth Node From End Of List</li>
+      <li><a href="Programs/Remove Nth Node From End of List.py">Remove Nth Node From End Of List</a> 
+        <p><b>Approach</b>: Use rabbit and tortoise method. Move rabbit n spaces, then move tortoise along with rabbit unitl rabbit reaches end of the list.
+        </p>
+      </li>
       <li>Reorder List</li>
     </ul>
   <h2>Matrix</h2>
