## Microsoft Interview Question

Software Engineer in TestsQuestion is not about retaining one node out of the duplicates, but deleting the entire duplicate nodes.

And

The 2 spl cases:

root is to be deleted

last element is to be deleted

all this missing in the above solution

I misunderstood the question, my bad, here's a solution for the given example:

```
void removeDupI(node*& head) {
if (head) {
node *tmp = head, *cur = head->next;
while (cur && cur->value == tmp->value) {
while (cur && cur->value == tmp->value) cur = cur->next;
tmp = cur;
if (cur) cur = cur->next;
}
while (head && head != tmp) cur = head, head = head->next, delete cur;
if (head == NULL) return;
node *prev = head, *test = head->next;
cur = test;
while (test) {
while (cur && cur->value == test->value) cur = cur->next;
while (test && test != cur) tmp = test, test = test->next, delete tmp;
if (cur) prev->next = cur;
if (cur && cur->next && cur->value != cur->next->value) prev = cur;
}
}
}
```

```
public LinkedNode RemoveDuplicates(LinkedNode head)
{
List<int> cs = new List<int>();
List<LinkedNode> ns = new List<LinkedNode>();
LinkedNode h = new LinkedNode(0);
LinkedNode t = h;
while (head != null)
{
ns.Add(head);
cs.Add(1);
if (ns.Count == 2)
{
if (ns[0].Data == ns[1].Data)
cs[1]++;
else
{
if (cs[0] == 1)
{
t.Next = ns[0];
t = ns[0];
t.Next = null;
}
}
ns.RemoveAt(0);
cs.RemoveAt(0);
}
head = head.Next;
}
if (ns.Count == 1 && cs[0] == 1)
t.Next = ns[0];
return h.Next;
}
1 > 2 > 3 > 3 > 4 > 4 > 5
1 > 2 > 5 // output
------------------------------------
1 > 1 > 2
2 // output
------------------------------------
1 > 1 > 1
// no output
------------------------------------
2 > 3 > 3 > 3
2 // output
Complexity is O(n) since we traverse list only once
```

@anonymous

grrrr888888!!!!!

even i cud obviously think the solution but your coding style really impressed me...

are you a very experienced coder????

Frankly speaking, I didn't like the coding style. It is hard to read.

Also, IMO, most experienced coders would avoid recursion in situations like these, unless they know that the linked list length would not get too large and even then they would probably avoid it.

(Hoping that compiler optimizes away tail recursive calls might not work every time. I am not sure if there are any compilers that do that)

What is the time complex to build a binary tree from array? It should be a solution to eliminate the repeat elements.

void RemoveDuplicated(node* HEAD){

node* previous_node=HEAD;

node* current_node = HEAD->next;

node* tmp_node=NULL;

bool just_deleted = false;

while(current_node){

tmp_node = current_node->next;

if(tmp_node && current_node->value == tmp_node->value){

current_node->next = tmp_node->next;

delete tmp_node;

just_deleted = true;

}

else {

if(just_deleted){

//delete current node

previous_node->next = current_node->next;

delete current_node;

current_node = previous_node->next;

just_deleted = false;

}

previous_node = current_node;

current_node = current_node->next;

}

}

If you don't post any explanation, at least don't post buggy code.

btw, the method signature

void RemoveDuplicated(Node *head)

can never work if you don't copy values around.

The head has the potential to change and even become NULL! You lose that information by not returning the new head, or not taking a Node ** pointer.

Your understanding is incorrect. Removing duplicates means, having unique values in the list... so 12222223 should be 1,2,3 and not 1,3!

Bool RemoveDuplicates( node** head )

{

If( head == NULL )

{

false;

}

node* cur = *head;

*head = NULL;

while(cur)

{

if(cur->next && cur->data == cur->next->data)

{

int curData = cur->data;

while(cur!= NULL && cur->data == curData)

{

node* temp = cur->next;

delete cur;

cur = cur->next;

}

continue;

}

if( !head )

head = cur;

cur = cur->next;

}

return true;

}

my soln:

remove_doup(list *head)

{

list *temp;

if(head->link)

{

if(head->data == head->link->data)

{

temp=head->link;

head=head->link->link;

free(k);

}

else

head=head->link;

remove_doup(head);

}

else

return ;

}

any wrong?....

```
public void RemoveDuplicate()
{
if (Head == null)
return;
Node c = Head;
Node prev = null;
bool deleteC = false;
while (c != null)
{
if (c.Next != null && c.Next.Value == c.Value)
{
c.Next = c.Next.Next;
deleteC = true;
}
else
{
if (deleteC)
{
if (prev == null)
Head = c.Next;
else
prev.Next = c.Next;
deleteC = false;
}
prev = c;
c = c.Next;
}
}
}
}
```

```
public void RemoveDuplicate()
{
if (Head == null)
return;
Node c = Head;
Node prev = null;
bool deleteC = false;
while (c != null)
{
if (c.Next != null && c.Next.Value == c.Value)
{
c.Next = c.Next.Next;
deleteC = true;
}
else
{
if (deleteC)
{
if (prev == null)
Head = c.Next;
else
prev.Next = c.Next;
deleteC = false;
}
prev = c;
c = c.Next;
}
}
}
}
```

//Non-recursive Soln

void removeDuplicates(List** head)

{

if (*head==NULL) return;

List* curr=*head;

while(1)

{

while (curr->next!=NULL&&curr->data ==curr->next->data)

{

List *temp =curr->next;

curr->next=curr->next->next;

delete temp;

}

if(curr->next!=NULL)

curr=curr->next;

else

break;

}

}

How about this?

```
void remove_sorted_duplicates (node *&n)
{
node *ptr = n;
node *target;
node *prev = NULL;
node *end;
int val;
while (ptr)
{
end = ptr->next;
val = ptr->data;
while (end && (end->data == val) )
{
delete ptr; //may be called multiple times, but delete NULL is ok
ptr = NULL;
target = end;
end = end->next;
delete target;
}
if (ptr) //unique node
{
if (prev)
prev->next = ptr;
else
n = ptr;
prev = ptr;
ptr=ptr->next;
}
else //duplicate node
{
if (!prev)
n = ptr;
ptr = end;
}
}
}
```

Basic algorithm is to delete all duplicates in the inner while loop. After that is a matter of setting previous/head/next ptrs.

Or how about this recursive version?

```
node *remove_sorted_duplicates2 (node *n)
{
node *end;
node *temp;
static int last_val_deleted;
static bool node_removed;
if (!n)
return n;
else
{
end = remove_sorted_duplicates2 (n->next);
if (end && (n->data == end->data) )
{
last_val_deleted = n->data;
node_removed = true;
temp=end->next;
delete end;
delete n;
n = temp;
}
else
{
if (node_removed && (n->data == last_val_deleted) )
{
delete n;
n = end;
}
else
n->next = end;
node_removed = false;
}
return n;
}
}
```

Basic algorithm is to delete "both" duplicates upon return. When duplicates are deleted a static flag to remember the last deleted node is set; so that we can handle "multiple" duplicates.

```
void RemoveDuplicateNodes(Node *& pStart)
{
Node* temp = pStart;
Node* old = NULL;
while(temp)
{
if((temp->m_pNext) && (temp->m_iValue == temp->m_pNext->m_iValue))
{
int iCurrentVal = temp->m_iValue;
while(true)
{
if(temp && (temp->m_iValue == iCurrentVal))
{
if(temp == pStart)
{
pStart = temp->m_pNext;
delete temp;
temp = pStart;
}
else
{
old->m_pNext = temp->m_pNext;
delete temp;
temp = old->m_pNext;
}
}
else
{
break;
}
}
}
else
{
old = temp;
temp = temp->m_pNext;
}
}
}
```

void dup()

{

revs *temp,*prev,*ne,*np;

if(start->i==start->next->i)

{

temp=start;

prev=temp->next;

start=start->next->next;

free(temp);

free(prev);

}

temp=start->next;

prev=start;

while(temp!=NULL)

{

if((temp->i)==(temp->next->i))

{

ne=temp;

np=temp->next;

prev->next=temp->next->next;

temp=prev->next;

free(ne);

free(np);}

else

{

prev=temp;

temp=temp->next;

}

}

return;

}

class CLink

{

int value;

class CLink* next;

}

CLink* RemDup(CLink* l)

{

if(!l)

return l;

CLink* t = l;

CLink* c;

while(t->next)

{

c = t->next;

//Find next different

while(t->value == c->value)

{

t->next = c->next;

//Delete a node, free memory (delete or free)

Delete(c);

}

t = c;

}

return l;

}

public Link DuplicateNodes(){

Link current = first;

int previousId = first.id;

while(current.next!=null)

{

if(current.id==current.next.id || previousId = current.id){

sysout("Duplicate Node Found");

delete_link(current.id);

current = current.next;

}else

current = current.next;

}

return current;

}

public Link Delete_Link (int key){

Link previous = first;

Link current = first;

while(current.id!=key){

if(current==null)

return null;

else{

previous = current;

current = current.next;

}

}

if(current == first)

first = first.next;

else

previous.next = current.next;

return current;

}

```
void remove_duplicates(node_t **list) {
while(*list) {
node_t *curr = *list;
if (curr->next && (curr->data == curr->next->data)) {
int data = curr->data;
while(curr && curr->data == data) {
node_t *tmp = curr;
curr = curr->next;
delete tmp;
}
*list = curr;
} else
list = &(*list)->next;
}
}
```

@nirmalr: Please help me understand this. Is list = head pointer ? Then in that case, your code modifies the head pointer. So although, your code does delete the duplicate nodes, the value of the head pointer would point to the last node of the new list with no duplicate values, i.e. if initial list was 1->1->1->2->3, your code would have the new list as 2->3 with head of the list as 3 not 2.

nice code, but you are loosing previous pointer. Suppose this is the eg: 1>2>2>2>2>3. When going to 2, you are loosing the pointer when you are doing this:

node_t *tmp = curr;

curr = curr->next;

delete tmp;

As in this eg. you are not connecting 1 to 3. Can you pls explain?

Here is the solution:

node* removeDupNew(node *cur){

bool mark = false;

node *newhead = cur, *temp, *prev = NULL;

while(cur) {

while(cur->next && cur->data == cur->next->data) {

mark = true;

temp = cur;

cur = cur->next;

delete temp;

}

if(mark) {

temp = cur;

cur = cur->next;

delete temp;

if(prev) prev->next = cur;

mark = false;

}

else {

if(!prev) newhead = cur;

prev = cur;

cur = cur->next;

}

}

if(!cur && !prev) return NULL;

return newhead;

}

How about this one.

Node * removeDup(Node * head){

Node* prev = NULL;

Node* cur = head;

Node* next = head->next;

while(cur!=null && next!=null){

if(cur && next && cur->value == next->value){

int data = next->value;

while(next->value == data){

Node* temp = next;

next=temp->next;

delete temp;

}

Node* tmp = cur;

cur = next;

next = cur->next;

delete tmp;

}else{

prev = cur;

cur = next;

next = cur->next;

}

if(next == null){

cur =null;

}

}

return head;

}

I think the following works:

```
Node *removeDup(Node *ptr) {
if (!ptr)
return NULL;
if (!ptr->next)
return ptr;
if (ptr->val != ptr->next->val) {
ptr->next = removeDup(ptr->next);
return ptr;
}
else {
while (ptr && ptr->next && ptr->val == ptr->next->val) {
Node *tmp = ptr->next;
delete ptr;
ptr = tmp;
}
Node *tmp = ptr->next;
delete ptr;
return removeDup(tmp);
}
}
```

void delete_duplicate()

{

node *temp=p;

node *old=-NULL;

while(temp)

{

if(temp->next !=NULL && temp->data==temp->next->data)

{

if(temp==p)

{

node *tmp=temp;

temp=temp->next;

delete tmp;

p=temp;

}

else

{

node *tmp=temp;

temp=temp->next;

old->next=temp;

delete tmp;

}

}

else

{

old=temp;

temp=temp->next;

}

}

}

```
void DeletDuplicates(Node **head)
{
Node *cur = *head;
Node *prev = null;
Node *temp1=null, *temp2 = null;
while(cur != null)
{
if(cur->next && cur->data==cur->next->data)
{
temp1 = cur; temp2 = cur->next;
cur = cur->next->next;
prev->next = cur;
free(temp1);
free(temp2);
}
else
{
prev = cur;
cur = cur->next;
}
}
```

//Need to add conditions to check if root node is a duplicate and needs to be deleted

Here is my implementation. Any comments are welcome!

void RemoveDup(node** head)

{

node* p = *head;

node* prev = NULL;

node* temp;

int deletedData = -1000;

while(p)

{

if((p->next && p->data == p->next->data) || p->data == deletedData)

{

if(!prev)

{

*head = p->next;

}

else

{

prev->next = p->next;

}

deletedData = p->data;

temp = p->next;

free(p);

p = temp;

continue;

}

prev = p;

p = p->next;

}

}

this code works ..except of this case ..

input- 1 1 2 2 3 4 5 5

output- 3 4 5

Reason: in my logic to remove the last left element in the duplicate chain I am copying the data to next node and then removing it from the list. However if it is the last node we don't have anything to copying in. Hence this bug.

mynode* reverse_recurse(mynode *root)

{

mynode *tempList=root;

int data,i,temp;

int truefalse;

while(tempList){

data=tempList->value;

truefalse=0;

while(tempList->next && data==(tempList->next)->value)

{

tempList->next=tempList->next->next;

truefalse=1;

}

if(truefalse && tempList->next) {

temp=tempList->next->value;

tempList->next->value=tempList->value;

tempList->value=temp;

tempList->next=tempList->next->next;

}

else if(truefalse && !tempList->next){

tempList->value=0;

}

else if(i=0 && truefalse) { root=tempList;

i++;

tempList=tempList->next; }

else { tempList=tempList->next; i++; }

}

return root;

}

Recurse(Node root)

{

if( root == null)

return null;

if(root.val == root.next.val)

{

int prevVal = root.Val;

// Find root

while((root != null) && (root.val == prevVal || root.next.val == root.val))

{

if( root.val!= prevVal)

prevVal = root.Val;

root = root.next;

}

if( root == null )

return null

}

// found root, assign next root

root.next = Recurse(Root.next);

return root;

}

1.Take two pointer p and q pointing to firstNode and secondNode.

2.if(q->info==(q->link)->info)

{

while((q->link)->info==(q->link->link)->info)

{

q=q->link;

}

delt all node from (next to p) to (q->link)

}

3.else

p-p_.link;

q=q->link;

-------------------------

it was just an approach to solve it... few cases are there which can be decorated wid this concept... lik

if first and second node are same... 11234

if list is empty/having singleNode

I try to simplify solutions so it's easy for me to build upon primitives. In this case I will create a method first that takes in a node and returns the next node that is non-duplicated or null if end of linked list is reached:

```
Node* FindNextDistinctNode (Node* startNode)
{
if (startNode == null)
{
return null;
}
int repeatedValue = startNode->Value;
Node currNode = startNode;
Node nextNode = startNode->Next;
while (nextNode != null)
{
if (currNode->Value == nextNode->Value)
{
currNode = nextNode;
nextNode = nextNode->Next;
}
else
{
if ((nextNode->Next == null) || (nextNode->Next->Value != nextNode->Value))
{
return nextNode;
}
else
{
currNode = nextNode;
nextNode = nextNode->Next;
}
}
}
return null;
}
```

Now it becomes to remove duplicates:

```
Node* RemoveDuplicates(Node* head)
{
Node * curr = head = FindDistinctNode(head);
while (curr)
{
curr->Next = FindDistinctNode(curr);
}
return head;
}
```

Complexity is O(n) since we traverse list only once

Correction:

```
Node* FindNextDistinctNode (Node* startNode)
{
if (startNode == null)
{
return null;
}
Node currNode = startNode;
Node nextNode = startNode->Next;
if (nextNode == null)
{
return startNode;
}
while (nextNode != null)
{
if (currNode->Value == nextNode->Value)
{
currNode = nextNode;
nextNode = nextNode->Next;
}
else
{
if ((nextNode->Next == null) || (nextNode->Next->Value != nextNode->Value))
{
return nextNode;
}
else
{
currNode = nextNode;
nextNode = nextNode->Next;
}
}
}
return null;
}
```

here is my solution in C#

public LinkedList RemoveDuplicate(LinkedList LL)

{

Node prev = null;

Node current = LL.First;

while (current != null)

{

Node temp = current;

while (temp.Link != null)

{

if (current.Data == temp.Link.Data)

{

temp.Link = temp.Link.Link;

if (current == LL.First)

{

LL.First = current.Link;

current = current.Link;

prev = LL.First;

}

else

{

prev.Link = current.Link;

prev = current.Link;

}

}

else

temp = temp.Link;

}

prev = current;

current = current.Link;

}

return LL;

}

/*My code in C...works 100% ;-) */

void keep_distinct()

{

NODE*temp,*ptr,*cur,*p;

int i,j,elem;

i=start->info;

p=(NODE*)malloc(sizeof(NODE));

p->info=i-1;

p->next=start;

start=p;

ptr=start;

temp=ptr->next;

cur=temp->next;

while(temp!=NULL)

{

if(temp->info==cur->info)

{

elem=temp->info;

ptr->next=temp->next;

free(temp);

temp=cur;

cur=cur->next;

}

else if(temp->info==elem)

{

elem=temp->info;

ptr->next=temp->next;

free(temp);

temp=cur;

cur=cur->next;

}

else

{

ptr=temp;

temp=cur;

cur=cur->next;

}

}

temp=start;

start=start->next;

free(temp);

}

node* remove_dup(node *head){

node *prev, *current, *ahead;

if(head == NULL)

return NULL;

if(head->next == NULL)

return head;

int count;

prev = NULL;

current = head;

ahead = current->next;

while(ahead != NULL){

count = 0;

while(ahead != NULL && current->data == ahead->data){

ahead = ahead->next;

count++;

}

if(count != 0){

if(ahead == NULL ){

if(prev == NULL){

head = ahead;

return head;

}else{

prev->next = ahead;

return head;

}

}

if(!prev){

head = current = ahead;

ahead = ahead->next;

continue;

}else{

prev->next = ahead;

current = ahead;

ahead = ahead->next;

continue;

}

}

prev = current;

current = ahead;

ahead = ahead->next;

}

return head;

}

```
void LinkedList::DeleteDuplicates()
{
Node * temp = head;
Node * nonDuplicateHead = 0;
Node * nonDuplicateCur = 0;
// Posit a negative leaning solution.. All are duplicates including head.. unless we say so.
// Always delete temp at the end of the loop if it is not null, and if the control variable is not flipped to false
bool shouldDeleteMe = false;
bool shouldDeleteNext = false;
while(temp!=0)
{
cout << "Processing Node " << temp->data;
Node* tempNext = temp->next;
if(tempNext != 0 && temp->data == tempNext->data)
{
shouldDeleteMe = true;
}
else
{
if(nonDuplicateHead == 0)
{
if(shouldDeleteNext == false)
{
nonDuplicateHead = temp;
}
else
{
nonDuplicateHead = temp->next;
}
}
if(nonDuplicateCur != 0)
{
if(shouldDeleteNext == false)
{
nonDuplicateCur->next = temp;
}
else
{
nonDuplicateCur->next = temp->next;
}
}
nonDuplicateCur = temp;
shouldDeleteMe = false;
}
if(shouldDeleteNext == true || shouldDeleteMe == true)
{
cout << " Deleting it";
Node *delHolder = temp;
temp = temp->next;
delete delHolder;
}
else
{
cout << " Skipping it";
temp = temp->next;
}
cout << endl;
shouldDeleteNext = shouldDeleteMe;
}
head = nonDuplicateHead;
tail = nonDuplicateCur;
}
```

I see so many big codes above, I think i have some approach.

1) Take 2 pointer.

P1 and P2.

2) Check if data is same then increment p2 by one.

3) Keep doing the step 2 until you find different data. (Also store the node in some temp variable and delete it)

4) If you get some unequal data on P2 then

p1->next = p2;

p= p2;

p2=p2->next;

do this till p2!=null.

```
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
void createList(int *arr,int size,struct node **root)
{
int i;
struct node *tail;
for(i=0;i<size;i++)
{
if(!(*root))
{
*root=(struct node*)malloc(sizeof(struct node));
(*root)->next=NULL;
(*root)->data=arr[i];
tail=*root;
}
else
{
tail->next=(struct node*)malloc(sizeof(struct node));
tail=tail->next;
tail->next=NULL;
tail->data=arr[i];
}
}
}
void traverse(struct node *root)
{
for(;root;printf("%d ",root->data),root=root->next);
printf("\n\n");
}
struct node *updateList(struct node *root)
{
struct node *p,*cur,*tail;
static struct node *newroot=NULL;
if(root==NULL)
return NULL;
cur=root;
while(cur)
{
if(cur->next && cur->data!=cur->next->data)
{
if(!newroot)
{
newroot=cur;
tail=cur;
}
else
{
tail->next=cur;
tail=tail->next;
}
cur=cur->next;
}
else
{
p=cur;
while(cur->next && cur->data== cur->next->data)
cur=cur->next;
if(p==cur)
{
if(!newroot)
{
newroot=cur;
tail=cur;
}
else
{
tail->next=cur;
tail=tail->next;
}
}
cur=cur->next;
}
}
tail->next=NULL;
return newroot;
}
int main()
{
int arr[]={1,1,1,2,3},size;//{1,2,3,3,4,4,5},size;
struct node *root=NULL;
createList(arr,sizeof(arr)/sizeof(arr[0]),&root);
traverse(root);
traverse(updateList(root));
return 0;
}
```

ideone.com/QVsBy

Node * rds(Node * node, Node * pre){

//last element

if(NULL==node)

return NULL;

//if the first element, we just compare it with the next one

if(NULL==pre){

if(NULL==node->next||node->data!=(node->next)->data){

node->next = rds(node->next,node);

return node;

}

else{

return rds(node->next,node);

}

}

// else we compare the current with prev and next

else{

// if next is NULL, just prev

if(node->next==NULL){

if(pre->data!=node->data)

return node;

else

return NULL;

}

else{

// compare to prev and next

if(pre->data!=node->data&&node->data!=(node->next)->data){

node->next = rds(node->next,node);

return node;

}

else{

return rds(node->next,node);

}

}

}

}

```
def remove_duplicates_sorted(self):
'''remove duplicates from sorted list '''
if self.head is None:
return False
node = self.head
# flag for duplicate removal
duplicate = False
remove_current = False
removed = False
while node.next:
duplicate = node.datum == node.next.datum
while duplicate and node.next:
node.datum = node.next.datum
node.next = node.next.next
remove_current = True
if node.next:
duplicate = node.datum == node.next.datum
# cleaning at the end
if not duplicate and remove_current:
node.datum = node.next.datum
node.next = node.next.next
remove_current = False
removed = True
# additional check if node.next exists
if not removed and node.next:
node = node.next
removed = False
if duplicate:
if node == self.head:
return None
return self
```

Tested on cases:

```
# test data for remove_duplicates_sorted
# case 1 - all unique
nodes1 = [Node(1), Node(2), Node(3), Node(4), Node(5)]
# case 2 - one double in the middle
nodes2 = [Node(1), Node(2), Node(3), Node(3), Node(4), Node(5)]
# case 3 - 2 double in the middle
nodes3 = [Node(1), Node(2), Node(2), Node(3), Node(3), Node(4), Node(5)]
# case 4 - double at the begining:
nodes4 = [Node(1), Node(1), Node(2), Node(3), Node(4), Node(5)]
# case 5 - more than double:
nodes5 = [Node(1), Node(2), Node(2), Node(2), Node(3), Node(4), Node(5)]
# case 6 - all the same:
nodes6 = [Node(1), Node(1), Node(1), Node(1), Node(1)]
list = LinkedList()
for node in nodes6:
list.add(node)
print list
print list.remove_duplicates_sorted()
```

del_node(Node *prev, Node *curr)

{

if (prev == NULL) {

free(curr);

return NULL;

} else {

prev->next = curr->next;

free(curr);

return prev;

}

}

Node *next,*curr,*prev=NULL;

while (curr != NULL) {

next = curr->next;

if ( curr ->value == curr->next->value || just_del == curr->value) {

just_del = curr->value;

prev = del_node(prev,curr);

curr = next;

} else {

prev = curr;

curr = next;

}

}

```
public Node removeDup(Node head){
if(head == null) return null;
Node newHead = null;
Node newEnd = null;
Node prev = head;
Node curr = head.getNext();
Node next = curr.getNext();
//process head
if(prev.getData() != curr.getData()){
newHead = prev;
newEnd = prev;
}
while(next != null){
if(prev.getData() != curr.getData()
&& curr.getData() != next.getData()){
if(newHead == null){
newHead = curr;
newEnd = curr;
}else{
newEnd.setNext(curr);
newEnd = curr;
}
}
prev = curr;
curr = next;
next = next.getNext();
}
//process tail
if(prev.getData() != curr.getData()){
if(newHead == null){
newHead = curr;
newEnd = curr;
}else{
newEnd.setNext(curr);
newEnd = curr;
}
}
newEnd.setNext(null);
return newHead;
}
```

This works. All case tested!

class Program

{

private static void RemoveDup(ref Node head)

{

if (head == null)

return;

Node current = head;

Node previous = null;

bool delete = false;

while (current.Next != null)

{

if (current.Val == current.Next.Val)

{

if (previous != null)

{

previous.Next = current.Next;

}

current = current.Next;

delete = true;

}

else

{

if (delete)

{

if (previous == null)

{

head = current.Next;

}

else

{

previous.Next = current.Next;

}

delete = false;

}

else

{

previous = current;

}

current = current.Next;

}

}

if (previous == null && delete == true)

{

head = null;

}

}

public class Node

{

private Node next;

public Node Next

{

get { return next; }

set { next = value; }

}

private int val;

public int Val

{

get { return val; }

set { val = value; }

}

public Node(int value)

{

this.val = value;

}

}

static void Main(string[] args)

{

Node head = new Node(1);

Node newNode1 = new Node(1);

Node newNode2 = new Node(1);

Node newNode3 = new Node(2);

Node newNode4 = new Node(3);

Node newNode5 = new Node(3);

Node newNode6 = new Node(4);

head.Next = newNode1;

newNode1.Next = newNode2;

newNode2.Next = newNode3;

newNode3.Next = newNode4;

newNode4.Next = newNode5;

newNode5.Next = newNode6;

RemoveDup(ref head);

}

}

- Anonymous July 29, 2009