bearvarine
BAN USERThis question has some ambiguity so the problem solver will have to clarify at least one fact.
The ambiguity is whether the idea of "repeated elements" means repeated adjacent to each other, or repeated anywhere in the list. The former case is solvable in O(n) but the latter case is essentially a sorting problem (due to the fact that building a hashtable or map is not allowed) so it probably can't be solved in less than O(n*log(n)).
The most straightforward solution is to simply use a nested loop, the outer loop pointing at each value in the linked list; and the inner loop pointing to each remaining value in the list. If a duplicate is found, you have to remove the duplicate node, which requires careful work with pointers. The downside is that complexity is O(n^2). The following C++ code ran successfully on VS2012.
#include <iostream> // cout
#include <Windows.h> // Sleep ()
using namespace std;
struct node
{
int val;
node * next;
node (int new_val) : val (new_val), next (nullptr)
{
}
~node ()
{
if (next) delete next;
}
void removeNext ()
{
if (next)
{
if (next->next)
{
node * n = next;
next = next->next;
n->next = nullptr;
delete n;
}
else
{
delete next;
next = nullptr;
}
}
}
void printList ()
{
int i = 0;
node * n = this;
while (n)
{
cout << i << ": " << n->val << endl;
n = n->next;
i++;
}
}
};
void removeDups (node * root)
{
node * c = root;
while (c)
{
node * x = c;
while (x)
{
if (x->next && c->val == x->next->val)
{
x->removeNext ();
}
else
{
x = x->next;
}
}
c = c->next;
}
}
void main (int argc, char ** argv)
{
node * root;
node * cur_node;
root = cur_node = new node (2);
cur_node->next = new node (4);
cur_node = cur_node->next;
cur_node->next = new node (6);
cur_node = cur_node->next;
cur_node->next = new node (4);
cur_node = cur_node->next;
cur_node->next = new node (2);
cur_node = cur_node->next;
cur_node->next = new node (2);
cout << "Original singly linked list:" << endl;
root->printList ();
removeDups (root);
cout << "After dups are removed:" << endl;
root ->printList ();
Sleep (30000);
}
All you are doing in your strategy is using a bit array as a type of sparse array to hold the found values in the linked list. This violates the constraint that no extra space be used. What if your integers were large numbers, or negative? Your strategy quickly breaks down.
- bearvarine August 22, 2013