CareerCup

1. first sort the linked list .then all duplicates will be together.
later remove one by one .this would be 0(n^2)order.
2.can be done by hash table.traverse the linked list and insert each
element in hash table.duplicates will cause collision.for small no this would be efficient.
3 .by using binary tree.create binary tree in 0(nlogn).while creating if any duplicate found print.
4.create min.heap.while creating check for duplicate.order will be same as the order of creation of heap.
5.split the llist in to 2 parts and then start comparisions one by one.

corrections and improvements are welcome

thanks
bhagwan@techmahindra.com

1) First sort the linked list.
Then traverse the list, by storing each nodes info value into a variable.
Compare the value of the variable with each node.
If there is a match, it means the element is duplicated.
--> The result will be O(n^2)

2) The aforementioned can be done using two pointers.
Sort the linked list.
The first one points to the first one in the list, whereas the second
pointer points to the second element in the list.
Move both pointers one step at a time and check for duplicates.
--> The result will be O(n^2)

Does anyone have O(n) answer?

Eila, If we are allowed a extra buffer memory, duplicates can be removed in O(n) using a hash table. In case no extra memory is allowed, we can do it in O(nlogn) using sort followed by a traversal. Once sorted you need to only compare consecutive values and delete if they match so this traversal will be o(n).

Can we sort the elements in a linked list in O(nlogn) time with out using any buffer? What is the algo.? I knew that Quicksort and merge sort can sort the elements present in an array in O(nlogn) time, but I am not sure about the algo. for linked list. Can someone give this algo?

We can create a binary search tree and insert the elements into it.Of course the duplicates will not get in.
It can be done in O(nlogn)

chiranjit.dutta@oracle.com

Creating one more binary search tree will take up some additional space ... right?
I cant think of anything better than O(n^2) if no additional space is allowed !
Please tell me if I am wrong or incase someone has better than O(n^2) solution.

I doubt there is something better than O(n^2).
Consider the following list of the lenght 3n:
1, 2, .. , n, -1, -2, .., -n, 1, 2, .., n.
To remove a pair of duplicates we need either to travel a length of 2n or to move n elements (negatives) outside. This is O(n) operations for O(n) elements

Quick sort on the linked list: O(nlogn) and it is in space. Then parse the sorted linked list and remove duplicate. Total O(nlogn)

Quicksort and linked list don't play well together. Quicksort depends on Partition which is best for random access memory. When it comes to sorting a linked list, Mergesort is the best.

Using mergesort, sort the linked list that takes O(nlogn) and then by doing linear comparisons remove the duplicates. O(nlogn) + O(n) = O(nlogn)

guys....do U have any test cases

In the previous post i put whole program

APPEND & JOIN are helping functins.

1.APPEND function append a node to a list.
and sets ptr to next node.

2. JOIN joins two lists.


3.MergeSort function devides the list into two lists recursively and sorts it using Function
merge

NOTE: in linked list we can add any node to a list
without using extra space. so there is no need of
extra spce
so merge sort of linked list can be done in O(nlogn) time without using extra space


1.void linklist :: APPEND(node ** ptr,node **head,node **tail){
if(*head == NULL){
*head = *ptr;
}
else{
(*tail)->next=*ptr;
}

*tail = *ptr;

*ptr=(*ptr)->next;

(*tail)->next = NULL;
}


2.void linklist :: JOIN(node **head_1,node **tail_1,node **head_2,node **tail_2){

if(*head_2 == NULL)
{
*tail_2=*tail_1;
(*tail_2)->next=NULL;
*tail_1=NULL;

}
else if(*head_1 == NULL)
{
*head_1=*head_2;
(*tail_2)->next = NULL;
*head_2=NULL;
}
else
{
(*tail_1)->next =*head_2;
*tail_1=NULL;
(*tail_2)->next = NULL;
*head_2=NULL;
}
}


3.void linklist :: MergeSort(){
if(p == NULL || p->next == NULL)
return;
p=MSort(p);
}

linklist :: node* linklist :: MSort(node* frst){
node* list1Head = NULL;
node* list1Tail = NULL;
node* list2Head = NULL;
node* list2Tail = NULL;

if((frst == NULL) || (frst->next == NULL))
return frst;
while(frst != NULL){
APPEND(&frst,&list1Head,&list1Tail);

if(frst != NULL)
APPEND(&frst,&list2Head,&list2Tail);
}

list1Head = MSort(list1Head);
list2Head = MSort(list2Head);

return merge(list1Head,list2Head);
}

4.
linklist :: node* linklist :: merge(node* list1, node* list2){

node *temp = NULL;
node *t =NULL;
node *pos = NULL;
if(list2==NULL)
return list1;

if(list1->data < list2->data){
temp=list1;
list1=list1->next;
}
else{
temp=list2;
list2=list2->next;
}

pos=temp;

while(list1!=NULL && list2 != NULL){
if(list1->data < list2->data){
t=list1;
list1=list1->next;
}
else{
t=list2;
list2=list2->next;
}
temp->next=t;
temp=t;
}
if(list1==NULL)
temp->next=list2;
else
temp->next=list1;
return pos;
}

I think pseudo code would have been a better option. Its difficult to trace this code.

Why don't you use Radix sort?

can we use heapsort? that is inplace sorting and works well for worst case too.

Here is a simple code in C#

using System;
using System.Collections.Generic;
using System.Text;

namespace Removeduplicates
{
class Removeduplicates
{
static void Main()
{
LinkedList<int> myll = new LinkedList<int>();
LinkedListNode<int> node1 = new LinkedListNode<int>(1);
myll.AddFirst(node1);
LinkedListNode<int> node2 = new LinkedListNode<int>(4);
myll.AddAfter(node1, node2);
LinkedListNode<int> node3 = new LinkedListNode<int>(2);
myll.AddAfter(node2, node3);
LinkedListNode<int> node4 = new LinkedListNode<int>(1);
myll.AddAfter(node3, node4);
LinkedListNode<int> node5 = new LinkedListNode<int>(4);
myll.AddAfter(node4, node5);
LinkedListNode<int> node6 = new LinkedListNode<int>(7);
myll.AddAfter(node5, node6);

LinkedListNode<int> current;

current = myll.First;
LinkedListNode<int> temp;
temp = current;

while (!(temp == null))
{
if (!(temp.Next == null) && !(current.Next == null))
{
if (temp.Value == current.Next.Value)
myll.Remove(current.Next);

current = current.Next;


}
else
{
temp = temp.Next;
current = temp;
}
}

current = myll.First;
while (!(current.Next == null))
{
for (int count = 0; count < myll.Count; count++)
{

Console.WriteLine(current.Value);

if (!(current.Next == null))
current = current.Next;
}
}
Console.Read();


}
}
}

You don't need to use AddAfter(), you could just have used AddLast() instead and saved yourself a lot of trouble by not having to remember the previous node.
Also, a static method with a generic parameter would have made the code many times better.

prints
1
4
2
7

We can create a binary tree(not search tree) from a linked list, so the left and right child of a[i] are a[2i] and a[2i+1]. While constructing this binary tree, before inserting a node, check if it is a duplicate and not insert in such case.

Once the binary tree is constructed from the linked list, doing a breadth first on the binary tree will restore the original list without the duplicates.

what is the final solution for the question "find the duplicate in unsorted array without using temp" ???

//C# 
using System;

    public class Node
    {
        public int value;
        public Node nextNode;

        public Node(int _value)
        {
            value = _value;
        }
    }

    public class linkedlist
    {
        Node firstNode;

        public linkedlist(int _value)
        {
            firstNode = new Node(_value);
        }

        public void add(int _value)
        {
            Node currentNode = firstNode;

            while (currentNode.nextNode != null)
            {
                currentNode = currentNode.nextNode;
            }
            currentNode.nextNode = new Node(_value);
        }

        public void print()
        {
            Node printnode = firstNode;
            while (printnode != null)
            {
                Console.WriteLine(" Value of Node is " + printnode.value);
                printnode = printnode.nextNode;
            }
        }

         

        public void removeDuplicates()
        {
            Node currentNode = firstNode;
            
            while (currentNode != null)
            {
                Node runnerNode = currentNode;
                Node previousRunnerNode = currentNode;
                while (runnerNode != null)
                {
                    if (currentNode.value == runnerNode.value)
                    {
                        previousRunnerNode.nextNode = runnerNode.nextNode;
                        runnerNode = runnerNode.nextNode;
                    }
                    else
                    {
                        previousRunnerNode = runnerNode;
                        runnerNode = runnerNode.nextNode;
                    }
                }
                currentNode = currentNode.nextNode;
            }
        }

    }

    class Program
    {
        static void Main(string[] args)
        {
            linkedlist MyLL = new linkedlist(0);
            MyLL.add(10);
            MyLL.add(8);
            MyLL.add(8);
            MyLL.add(4);
            MyLL.add(8);
            MyLL.add(6);
            MyLL.print();
            MyLL.removeDuplicates();
            Console.WriteLine("After Removing duplicates");
            MyLL.print();
            Console.Read();
        }
    }

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<stack>
using namespace std;
struct Node{
int data;
struct Node* next;
};
struct Node * head;
void print(struct Node* temp)
{
int i=0;
cout<<"head->";
while(temp!= NULL)
{
cout<<temp->data<<"->";
temp =temp->next;
i++;
}
cout<<"NULL";

}




void list_remove_dup(Node * head)
{ struct Node *current;
struct Node *previous;
struct Node *runner;
struct Node *tmp;
if(head == NULL) return;
if(head->next == NULL) return;
current = head->next;
previous = head;
while(current != NULL){
runner = head;
while(runner != current){
// remove node if equal
if(runner->data == current->data){
tmp = current;
current = current->next;
previous->next = current;
delete tmp;
break;
}runner = runner->next;
}if(runner == current){
current = current->next;
previous = previous->next;
}
}
}




int main()
{

head = NULL;
Node* first = new Node;
Node* second = new Node;
Node* third = new Node;
Node* fourth = new Node;

Node * five = new Node;
Node * six = new Node;
Node * seven = new Node;
Node * eight = new Node;
Node * nine = new Node;
Node * ten = new Node;


head =first;
first->data = 1;
first->next = second;
second->data = 2;
second->next = third;
third->data = 1;
third->next = fourth;
fourth->data=3;
fourth->next =five;
five->data = 4;
five->next = six;
six->data = 3;
six->next = seven;
seven->data = 6;
seven->next = eight;
eight->data = 9;
eight->next = nine;
nine->data = 7;
nine ->next =ten;
ten->data =9;
ten->next =NULL;

print(head);
cout<<endl;

list_remove_dup(head);
print(head);
cout<<endl;


}

please make me understand - what does it mean to do not use extra buffer?

Solution--
Step 1- Create TreeSet .
Step 2- Insert every element in it, duplicates will be out. as Set does not contain duplicate element.

here is algo to sort a linked list in O(nlogn)


#include <iostream.h>

class linklist
{
private:

struct node
{
int data;
node *next;
};

node *p;

void quick(node **,node **);
void APPEND(node **,node **,node **);
void JOIN(node **,node **,node **,node **);
node* merge(node*,node*);
node* MSort(node*);
node* recreverse(node*);
public:

linklist();
void append( int num );
int count();
void del( int num );
void display();
void Qsort();
void MergeSort();
void reverse(); //reverses recursively
void Middle();

~linklist();
};

linklist::linklist(){

p=NULL;
}

void linklist::append(int num){

node *q,*t;

q = new node;
q->data=num;
q->next=NULL;


if( p == NULL )
p=q;
else
{
t = p;
while( t->next != NULL )
t = t->next;
t->next=q;
}
}


void linklist::del( int num ){

node *q,*r;

q=p;
r=NULL;

if(p == NULL){
cout << endl << "List is EMPTY" << endl;
return;
}


while(q->data != num && q->next != NULL){
r=q;
q=q->next;
}

if(q->data != num){
cout << endl << "Number not present in List" << endl;
return;
}

if(r == NULL)
p=q->next;
else
r->next=q->next;

delete q;
cout << endl << "Number deleted" << endl;
}

void linklist::display(){

node *q;
cout << endl << "data: ";

for( q = p ; q != NULL ; q = q->next )

cout<< q->data << " ";

cout << endl;

}

int linklist::count()
{
node *q;
int c=0;
for( q=p ; q != NULL ; q = q->next )
c++;

return c;
}

void linklist :: Qsort(){
if(p == NULL || p->next == NULL)
return;
node *temp = p;

while(temp->next){
temp = temp->next;
}
quick(&p,&temp);
}


void linklist :: quick(node ** frst,node **last){
node * lesHead = NULL;
node * lesTail = NULL;
node * equHead = NULL;
node * equTail = NULL;
node * larHead = NULL;
node * larTail = NULL;
node * current= *frst;
node * temp = NULL;

int pivot,info;
if((current) == NULL)
return;
pivot=(current)->data;
APPEND(&current,&equHead,&equTail);

while(current != NULL){
info = current->data;
if(info < pivot)
APPEND(&current,&lesHead,&lesTail);
else if(info > pivot)
APPEND(&current,&larHead,&larTail);
else
APPEND(&current,&equHead,&equTail);
}
quick(&lesHead,&lesTail);
quick(&larHead,&larTail);

JOIN(&lesHead,&lesTail,&equHead,&equTail);
JOIN(&lesHead,&equTail,&larHead,&larTail);

if(frst != NULL)
*frst = lesHead;
if(last != NULL)
*last = larTail;

p = lesHead;
return;
}



void linklist :: APPEND(node ** ptr,node **head,node **tail){
if(*head == NULL){
*head = *ptr;
}
else{
(*tail)->next=*ptr;
}

*tail = *ptr;

*ptr=(*ptr)->next;

(*tail)->next = NULL;
}


void linklist :: JOIN(node **head_1,node **tail_1,node **head_2,node **tail_2){

if(*head_2 == NULL)
{
*tail_2=*tail_1;
(*tail_2)->next=NULL;
*tail_1=NULL;

}
else if(*head_1 == NULL)
{
*head_1=*head_2;
(*tail_2)->next = NULL;
*head_2=NULL;
}
else
{
(*tail_1)->next =*head_2;
*tail_1=NULL;
(*tail_2)->next = NULL;
*head_2=NULL;
}
}


void linklist :: MergeSort(){
if(p == NULL || p->next == NULL)
return;
p=MSort(p);
}

linklist :: node* linklist :: MSort(node* frst){
node* list1Head = NULL;
node* list1Tail = NULL;
node* list2Head = NULL;
node* list2Tail = NULL;

if((frst == NULL) || (frst->next == NULL))
return frst;
while(frst != NULL){
APPEND(&frst,&list1Head,&list1Tail);

if(frst != NULL)
APPEND(&frst,&list2Head,&list2Tail);
}

list1Head = MSort(list1Head);
list2Head = MSort(list2Head);

return merge(list1Head,list2Head);
}

linklist :: node* linklist :: merge(node* list1, node* list2){

node *temp = NULL;
node *t =NULL;
node *pos = NULL;
if(list2==NULL)
return list1;

if(list1->data < list2->data){
temp=list1;
list1=list1->next;
}
else{
temp=list2;
list2=list2->next;
}

pos=temp;

while(list1!=NULL && list2 != NULL){
if(list1->data < list2->data){
t=list1;
list1=list1->next;
}
else{
t=list2;
list2=list2->next;
}
temp->next=t;
temp=t;
}
if(list1==NULL)
temp->next=list2;
else
temp->next=list1;
return pos;
}



void linklist :: reverse(){
if((p==NULL)||(p->next==NULL))
return;

p=recreverse(p);


}

/*linklist :: node* linklist :: recreverse(node *ptr){
node *temp=NULL;
static node *base=NULL;
static node *retptr=NULL;
if(base==NULL)
base=ptr; ///MINE
if(ptr->next==NULL)
{
retptr=ptr;
return ptr;
}

temp=ptr->next;

recreverse(temp)->next=ptr;
if(ptr==base){
ptr->next=NULL;
base=NULL;
return retptr;
}
return ptr;
}*/


linklist :: node* linklist :: recreverse(node * n)
{
node * m ;

if (!(n->next))
return n ;

m = recreverse(n->next) ;
n->next->next = n ;
n->next = NULL ;
return m ;
}


void linklist :: Middle(){
node* sing=NULL;
node* doub=NULL;

if(p == NULL){
cout << endl << "List is EMPTY" << endl;
}

else if(p->next == NULL){
cout << endl << "Middle Element :" << p->data << endl;
}
else{
sing=p;
doub=p;

while(doub->next && doub->next->next){
doub=doub->next->next;
sing=sing->next;
}

if(doub->next==NULL)
cout << endl << "Middle Element :" << sing->data << endl;
else
cout << endl << "Middle Elements :" << sing->data << " and " << sing->next->data << endl;
}
}


linklist::~linklist()
{
node *q;

if( p == NULL )
return;

while( p != NULL ){
q = p->next;
delete p;
p = q;
}
}

void main()
{
linklist ll;

int choice=1;
while(choice)
{
cout << "to_append press 1" << endl;
cout << "to_delete press 2" << endl;
cout << "to_count press 3" << endl;
cout << "to_display press 4" << endl;
cout << "to_sort(Quick) press 5" << endl;
cout << "to_sort(Merge) press 6" << endl;
cout << "to_reverse press 7" << endl;
cout << "to_getMiddle press 8" << endl;

cout << "to_exit press 0" << endl;
cout << "Your Choice: " << endl;

while(scanf("%d",&choice) != 1 || choice < 0 || choice > 8 || getchar() != '\n'){
while(getchar() != '\n');
printf("\nWrong Input!!!! Enter again: ");
}
switch(choice){

case 1:
int num;
cout<< "\nnumber: " << endl;
while(scanf("%d",&num) != 1 || getchar() != '\n'){
while(getchar() != '\n');
printf("\nWrong Input!!!! Enter again: ");
}

ll.append(num);

break;

case 2:
cout << "\nnumber: " << endl;
while(scanf("%d",&num) != 1 || getchar() != '\n'){
while(getchar() != '\n');
printf("\nWrong Input!!!! Enter again: ");
}
ll.del(num);

break;

case 3:

cout << "\nNo of elements: " << ll.count() << endl;

break;

case 4:
ll.display();

break;

case 5:
ll.Qsort();
cout << "Linklist Sorted :To display sorted list press 4" << endl;

break;

case 6:
ll.MergeSort();
cout << "Linklist Sorted :To display sorted list press 4" << endl;

break;

case 7:
ll.reverse();
cout << "Linklist reversed :To display reversed list press 4" << endl;

break;

case 8:
ll.Middle();

break;

case 0:

break;

default:
cout << "Wrong choice" << endl;

}

}
}



rpandey@cdotd.ernet.in