vivekh
BAN USER1) iterate through the list (while node->value! = 'f'), if you find a char ( this can be checked by if node->value == 'c' and so on) delete it from its current position and insert it to the tail of the list. after the first iteration the lists looks like this
1- 2-3-4-5-6-a-b-c-d-e-f
2) take two pointers one pointing to head(p1) and another pointing to middle+1(p2) position. iterate p1 till the middle. for each iteration insert p2 between p1 and p1->next, for eg insert a between 1 and 2 , insert b between 2 and 3 and so on.After the iteration the list would become
1-a-2-b-3-c-4-d-5-e-6-f
//h1 = head of first link list
//h2 = head of second link list
LIST *merge_linklist(LIST *h1, LIST* h2){
LIST* h3 == NULL; // head of the merged list
LIST *trav,*node; //temporary pointer
if(h1==NULL && h2==NULL)
return NULL;//return NULL if both list are empty
if(h1==NULL)
return h2;
else if(h2==NULL)
return h1
while (h1!=NULL && h2!=NULL) {
//check in the next element is same
//as the previos one
if (h1->value = h1->next->value) {
h1=h1->next;
continue; //ignore the element
}else if (h2->value = h2->next->value) {
h2=h2->next;
continue; //ignore the element
}
if(h1->value < h2->value){
//create a node for final merge list
if(h3 == NULL){
h3 = (LIST*) malloc(sizeof(LIST));
h3->value = h1->value // store the smaller of h1 and h2 into h3
h3->next = NULL;
trav = h3;
}else{
node = (LIST*) malloc(sizeof(LIST));
node->value = h1->value;
trav->next = node;
trav = trav->next;
node->next = NULL;
}
h1= h1->next;
}else if(h1->value > h2->value){
if(h3 == NULL){
h3 = (LIST*) malloc(sizeof(LIST));
h3->value = h2->value // store the smaller of h1 and h2 into h3
h3->next = NULL;
trav = h3;
}else{
node = (LIST*) malloc(sizeof(LIST));
node->value = h2->value;
trav->next = node;
trav = trav->next;
node->next = NULL;
}
h2=h2->next; //move the pointer of the list having the smaller value
}else{// when h1 and h2 are equal
if(h3 == NULL){
h3 = (LIST*) malloc(sizeof(LIST));
h3->value = h2->value // store the either h1 or h2 into h3
h3->next = NULL;
trav = h3;
}else{
node = (LIST*) malloc(sizeof(LIST));
node->value = h1->value;
trav->next = node;
trav = trav->next;
node->next = NULL;
}
h1=h1->next;
h2=h2->next;
}
}//while loop ends
//trav points to tail of the merged list h3
//now we need to attach the tail of h3 to the left over element of the longer list
(h1==NULL) ? (trav->next=h2->next):(trav->next=h1->next);
return h3; // return the head of the merged list
}
//h1 = head of first link list
//h2 = head of second link list
LIST *merge_linklist(LIST *h1, LIST* h2){
LIST* h3 == NULL; // head of the merged list
LIST *trav,*node; //temporary pointer
if(h1==NULL && h2==NULL)
return NULL;//return NULL if both list are empty
if(h1==NULL)
return h2;
else if(h2==NULL)
return h1
while (h1!=NULL && h2!=NULL) {
//check in the next element is same
//as the previos one
if (h1->value = h1->next->value) {
h1=h1->next;
continue; //ignore the element
}else if (h2->value = h2->next->value) {
h2=h2->next;
continue; //ignore the element
}
if(h1->value < h2->value){
//create a node for final merge list
if(h3 == NULL){
h3 = (LIST*) malloc(sizeof(LIST));
h3->value = h1->value // store the smaller of h1 and h2 into h3
h3->next = NULL;
trav = h3;
}else{
node = (LIST*) malloc(sizeof(LIST));
node->value = h1->value;
trav->next = node;
trav = trav->next;
node->next = NULL;
}
h1= h1->next;
}else if(h1->value > h2->value){
if(h3 == NULL){
h3 = (LIST*) malloc(sizeof(LIST));
h3->value = h2->value // store the smaller of h1 and h2 into h3
h3->next = NULL;
trav = h3;
}else{
node = (LIST*) malloc(sizeof(LIST));
node->value = h2->value;
trav->next = node;
trav = trav->next;
node->next = NULL;
}
h2=h2->next; //move the pointer of the list having the smaller value
}else{// when h1 and h2 are equal
if(h3 == NULL){
h3 = (LIST*) malloc(sizeof(LIST));
h3->value = h2->value // store the smaller of h1 and h2 into h3
h3->next = NULL;
trav = h3;
}else{
node = (LIST*) malloc(sizeof(LIST));
node->value = h1->value;
trav->next = node;
trav = trav->next;
node->next = NULL;
}
h1=h1->next;
h2=h2->next;
}
}//while loop ends
//trav points to tail of the merged list h3
//now we need to attach the tail of h3 to the left over element of the longer list
(h1==NULL) ? (trav->next=h2->next):(trav->next=h1->next);
return h3; // return the head of the merged list
}
if ( node->next! = NULL) { // check if the node is not the last node
while(node->next!=NULL){
node->value = node->next->value;
if(node->next->next == NULL) {// check if the node is the second last node
free(node->next); // always free the last node after adjusting node-> value
node->next = NULL;
break;
}
node= node->next
}
}else { // if the node is the last node
NODE * temp;
temp = node;
node =NULL;
free(temp);
}
please dont make assumptions while devising a solution.it would be too easy if u can change the node structure. link list means singly link list unless stated otherwise.
- vivekh February 07, 2012