CareerCup

take three pointers one, two and three.
first of all search for a 1 and move( delete from current) it to head (if 1 is already at head then omit this step)
now traverse the list starting from 2nd node
if found 1 delete it and move it to the head (update the head also)
if found 2 dont do anything just move to nect node.
if found 3 move it to last .

why so much...

take 3 int variables.. count the occrence of each digit in the first parse of link list....
in the second parse replace the node value as the number of occrance of 1 then 2 and then 3....

2 pointers original_head, original_tail

1. orignal_head = head;
2. Traverse DLL from tail to original_head.
2a. If nodeValue = value 1 ; move node to head (start).

# original_head is required because in step 2a we add the node to beginning (head), thereby changing value of head. Without original_head we would be stuck in an endless loop.

3. orignal_tail = tail;
4. Traverse DLL from original_head to original_tail.
4a. If nodeValue = value 3 ; move node to tail (end).

# Value 2 falls in place by itself.

Complexity: O(n) + O(n) = O (n)

instead of keeping 3 separate lists and merging it in last . Keep two check-points which marks end 1's, and 2's . now you traverse the list , when ever you find a 1, detach it from current position and attach to 1's check point, same thing for 2's. after you traversed the list once , it will be sorted.

My solution

public class sampleSort123 {

	private static headNode = null;
	private static tailNode = null;
	
	// ASSUMPTION: headNode and tailNode are given to us.

	public static moveToHead(Node node) {
		// Disconnect the node from the doubly linked list
		Node leftNode = node.getLeftNode();
		Node rightNode = node.getRightNode();
		
		leftNode.setRightNode(rightNode);
		rightNode.setLeftNode(leftNode);
		
		headNode.setLeftNode(node);
		headNode = node;
		
		return;
	}
	
	public static moveToTail(Node node) {
		// Let the address be of Long type
		// Disconnect the node from the doubly linked list
		Node leftNode = node.getLeftNode();
		Node rightNode = node.getRightNode();
		
		leftNode.setRightNode(rightNode);
		rightNode.setLeftNode(leftNode);
		
		tailNode.setRightNode(node);
		tailNode = node;
		
		return;
	}
	
	private static sort123Array() {
		Node currentNode = headNode;
		
		while(currentNode.getRightNode != null) {
			if(currentNode.getValue() == 1) 
				moveToHead(currentNode);
			else if(currentNode.getValue() == 3)
				moveToTail(currentNode);
		}
	}
}

take 3 pointers to store 3 link lists for 1,2,3,
now start deleting all the nodes from the link list and instead of freeing the deleted node, append it to proper pointer above mentioned.
Then finally merge the lists

How about this?

Node sort(Node head)
{
Node typeA = new Node (1);
Node headA = typeA;
Node typeB = new Node (2);
Node headB = typeB;
Node typeC = new Node (3);
Node headC = typeC;
Node current = head;

while(current! = null)
{
if(current.Value == typeA.value)
{
typeA.next = new Node(current.value);
typeA = typeA.next;
}
else if(current.Value == typeB.value)
{
typeB.next = new Node(current.value);
typeB = typeB.next;
}
else if(current.Value == typeC.value)
{
typeC.next = new Node(current.value);
typeC = typeC.next;
}

}
Node tmp = headA;
headA = headA.next;
Node tmp = headB;
headB = headB.next;
Node tmp = headC;
headC = headC.next;

//combining the 3 parts
typeA.next = headB;
typeB.next = headC;

return headA;

}

oops! forgot to progress the current pointer

Node sort(Node head)
{
        //make 3 dummy nodes 
	Node typeA = new Node (1);
	Node headA = typeA;
	Node typeB = new Node (2);
	Node headB = typeB;
	Node typeC = new Node (3);
	Node headC = typeC;
	Node current = head; 

	while(current! = null)
	{
		if(current.Value == typeA.value)
		{
			typeA.next = new Node(current.value);
			typeA = typeA.next;
		}
		else if(current.Value == typeB.value)
		{
			typeB.next = new Node(current.value);
			typeB = typeB.next;
		}
		else if(current.Value == typeC.value)
		{
			typeC.next = new Node(current.value);
			typeC = typeC.next;
		}
		current = current.next;
	}
       //deleting the first dummy nodes
	Node tmp = headA;
	headA = headA.next;
	Node tmp = headB;
	headB = headB.next;
	Node tmp = headC;
	headC = headC.next;
	
	//combining the 3 parts
	typeA.next = headB;
	typeB.next = headC;

	return headA;

}

Must cosider the fact that the given link list is doubly. So, we can easily implement this in the same fashion as for grouping 1,2,3 together in an array.

Above stated methods are true for single link list.

Must consider the fact that the given link list is doubly. So, we can easily implement this in the same fashion as for grouping 1,2,3 together in an array.

Above stated methods are true for single link list.

What about having 3 variables reprenting the number of occurences for 1, 2 and 3 in the list. Then just traverse the list counting 1s and 2s and 3s. Once ended create a new list with as many nodes as the counters describe

<pre lang="" line="1" title="CodeMonkey46359" class="run-this">class SortLinkedList {
public Node sort123(Node head) {
Node[] starters = new Node[3];
Node firstNode = head;
do {
Node next = head.getNext();
head.setNext(head);
head.setPrev(head);
Node curNode = starters[head.getData() - 1];
if (curNode == null) {
starters[head.getData() - 1] = head;
} else {
Node lastNode = curNode.getPrev();
lastNode.setNext(head);
head.setPrev(lastNode);
head.setNext(curNode);
curNode.setPrev(head);
}
head = next;
} while (firstNode != head);

firstNode = null;
for (int i = 0; i < 3; ++i) {
Node curNode = starters[i];
if (curNode != null) {
if (firstNode == null) {
firstNode = curNode;
} else {
Node prevLast = firstNode.getPrev();
Node lastCur = curNode.getPrev();
prevLast.setNext(curNode);
curNode.setPrev(prevLast);
lastCur.setNext(firstNode);
firstNode.setPrev(lastCur);
}
}
}
return firstNode;
}
}</pre><pre title="CodeMonkey46359" input="yes">
</pre>

American Flag, Link list version???

Move 1's to head, Move 3 to tail

Duplicate for qns 11561969

People Proposing so complex ,

1st dutch nation flag problem but it requires the swapping elements isn't it ?

what else we can do , take 3 counter , traverse linked list , count for each 1,2,3
then just put 1 , 2, 3 on basis of corresponding counter isn't it ?

correct me if anything ?

Shashank

//Recursive sort doubly link list

node* sortDoubly(node *head)
{
node*ptr2=NULL,*ptr3=NULL, *ptr4=NULL, *headprev=NULL;
if (!head)
{ return NULL;
}

else if(head->next==NULL)
{
return head;
}


//ptr2=ptr->next;
ptr2=sortDoubly(head->next);
if(head->a > ptr2->a)
{ headprev=head->back;
ptr2->back=headprev;
headprev->next=ptr2;
ptr3=ptr2;
while(ptr3->next && head->a > ptr3->a )
{
ptr3=ptr3->next;
}
if (ptr3->next)
{
ptr4=ptr3->back;
ptr4->next=head;
head->back=ptr4;
head->next=ptr3;
ptr3->back=head;
return ptr2;
}

else
{
ptr3->next=head;
head->next=NULL;
head->back=ptr3;
return ptr2;
}
}

return head;


}

void sort(node p)
{
node r=null;
int i=0;
p=firstaddress;
boolean b=true;
while(b==true)
{
b=false;
p=firstaddress;

r=null;
i=0;
while(p!=null)
{
i++;
node q = p.next;
show(p);
System.out.println("\n");
if(q==null)
{
break;
}
else
{
if(p.val>q.val)
{
b=true;
r=p.prev;
if(r!=null)
r.next=q;
p.prev=q;
p.next=q.next;
if(q.next!=null)
q.next.prev=p;
q.prev=r;
q.next=p;

if(i==1)
firstaddress=q;

}
else
{
if(i==1)
firstaddress=p;
p=p.next;
}
}
}
}
}
not bothering aout the time complexcity..o(n2)

Check it, working correct:


#include<iostream>
#include<string.h>

using namespace std;
class Node{
public:
int n;
Node *next,*prev;
Node(int i){
n=i;
next=prev=NULL;
}
};
class dll{
public:
Node *head;
dll(){
head=NULL;
}
void insert(int i){
Node *n=new Node(i);
if(head==NULL) {head=n;return;}
Node *temp=head;
while(temp->next!=NULL) temp=temp->next;
temp->next=n;
n->prev=temp;
}
void display(){
Node *temp=head;
while(temp!=NULL){
cout<<temp->n<<" --> ";
temp=temp->next;
}
cout<<endl;
}
};
void correct(dll list,Node *temp){

Node *tmp=temp->next;
temp->next=tmp->next;
if(temp->next!=NULL) temp->next->prev=temp;
Node *tmp2=temp;
while(tmp2!=NULL&&tmp2->prev!=NULL){ if(tmp2->prev->n<=tmp->n){break;}tmp2=tmp2->prev;}
if(tmp2==NULL){tmp->next=list.head;
list.head->prev=tmp;
list.head=tmp;}
else{
tmp->prev=tmp2->prev;
tmp2->prev->next=tmp;
tmp->next=tmp2;
tmp2->prev=tmp;
}
}
void sort(dll list){
list.display();
cout<<endl;
Node *temp=list.head;

temp=list.head->next;
while(temp!=NULL&&temp->next!=NULL){
if(temp->n>temp->next->n){
correct(list,temp);
continue;
}
temp=temp->next;
}
cout<<endl<<"Sorted: "<<endl;
list.display();
}

int main(){
dll list;
int str[]={1,3,2,1,2,3,2,1,1};
int size=sizeof(str)/sizeof(int);
for(int i=0;i<size;i++){
list.insert(str[i]);
}
sort(list);
cout<<endl;
system("pause");
return 0;
}

We can implement this Quicksort style - use 2 as pivot to shove all 1's to the left and 3's to the right.

A Naive solution:

Take three copies of the list, one for each of the three numbers. Eg, First list for 1, Second for 2, and Third for 3.

Traverse each linked list deleting elements other than the one it represents.
Then append all three lists in sorted order.

This has O(kn) running time and O(kn) space complexity, where 'k' is the number of unique elements (in this case - 1,2 and 3).