Time: 8 ms (44.48%), Space: 10.7 MB (74.80%) - LeetHub

JanaSabuj · JanaSabuj · commit e0edb660a50a · 2022-08-14T11:00:56.000+05:30
diff --git a/19-remove-nth-node-from-end-of-list/19-remove-nth-node-from-end-of-list.cpp b/19-remove-nth-node-from-end-of-list/19-remove-nth-node-from-end-of-list.cpp
@@ -0,0 +1,44 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     ListNode *next;
+ *     ListNode() : val(0), next(nullptr) {}
+ *     ListNode(int x) : val(x), next(nullptr) {}
+ *     ListNode(int x, ListNode *next) : val(x), next(next) {}
+ * };
+ */
+typedef struct ListNode node;
+class Solution {
+public:
+    ListNode* removeNthFromEnd(ListNode* head, int n) {
+        node* dummy = new node(0);
+        dummy->next = head;
+
+        node* right = head;
+        node* left = head;
+        node* prev = dummy;
+
+        // [-------------------------------]
+        //      n                L-n             
+        // [-------------|-----------------]
+        //      L-n         |     n
+
+        int cnt = n;
+        while(right != NULL and cnt--) {
+            // right traverses n steps
+            right = right->next; 
+        }
+
+        while(right != NULL) {
+            // right traverses (L-n) steps
+            right = right->next;
+            prev = left;
+            left = left->next;
+        }
+
+        prev->next = left->next;
+
+        return dummy->next;
+    }
+};
