[C++] Iterative 2 Pointer Solution Explained, ~100% Time, 40% Space
This problem is rather easy to solve with extra memory and possibly an extra pass; a better challenge comes from trying to trying to work under more constrained
This problem is rather easy to solve with extra memory and possibly an extra pass; a better challenge comes from trying to trying to work under more constrained requirements.\n\nFirst of all we will declare a few support variables:\n* `res` will be the base from which we will build our solution and will save us a bit of painful edge cases to otherwise consider, for the affordable cost of one extra node;\n* `prev` and `iter` will be the 2 pointers we will use to parse and purge the list from duplicates;\n* `currVal` is a convenience variable to store the currently parsed value.\n\nWe will attach `head` right after `res` and then move on with a main loop that will run as long as we have `prev && prev->next`, in which:\n* we will prepare the ground for the next inner loop, setting `iter` right after `prev` and assigning `iter->val` to `currVal`;\n* advance `iter` with our inner loop, as long as we still have `iter->next` and its value matches the one stored in `currVal`;\n* we will then have 2 cases:\n\t* the loop never run, since we only have one node with `currVal` right after `prev`, so this very node will become our `prev` for the next iteration;\n\t* otherwise, it means we found multiple occurrences of the same value and then we will just have to slice them away frome the list: in the next iteration `prev` will stay the same (so, potentially it might always be just `res`) and its successor will be the next node with a different value than `currVal`.\n\nOnce we are done, we can return `res->next` :)\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    ListNode* deleteDuplicates(ListNode* head) {\n        // support variables\n        ListNode *res = new ListNode(-101), *prev = res, *iter = head;\n        int currVal;\n        // attaching res before head\n        res->next = head;\n        while (prev && prev->next) {\n            // preparing for the inner loop\n            iter = prev->next;\n            currVal = iter->val;\n            // advancing with all the similar values\n            while (iter->next && iter->next->val == currVal) iter = iter->next;\n            // case 1: only one node with currVal\n            if (iter == prev->next || !iter) prev = iter;\n            else prev->next = iter->next;\n        }\n        return res->next;\n    }\n};\n```\n\nAnd since it just occurred to me that with my last version of the code `currVal` has little use, refactor without it - performance is clearly basically the same, despite saving a few bytes and assignments:\n\n```cpp\nclass Solution {\npublic:\n    ListNode* deleteDuplicates(ListNode* head) {\n        // support variables\n        ListNode *res = new ListNode(-101), *prev = res, *iter = head;\n        // attaching res before head\n        res->next = head;\n        while (prev && prev->next) {\n            // preparing for the inner loop\n            iter = prev->next;\n            // advancing with all the similar values\n            while (iter->next && iter->next->val == iter->val) iter = iter->next;\n            // case 1: only one node with the same value\n            if (iter == prev->next || !iter) prev = iter;\n            // case 2: multiple nodes with the same value found\n            else prev->next = iter->next;\n        }\n        return res->next;\n    }\n};\n```
['Two Pointers', 'C', 'Iterator', 'C++']