I\'m strugling with writing this linked list function for my intro to C class. A

Question

 I'm strugling with writing this linked list function for my intro to C class. Any help?  /** TODO  * function:  lst_merge_sorted  *  * description:  assumes both list a and b are in  *      sorted (non-descending) order and merges them  *      into a single sorted list with the same  *      elements.    *  *      This single sorted list is stored in a while  *      b becomes empty.  *  *      if either of given lists are not sorted,   *      we blame the caller and the behavior is  *      implementation dependent -- i.e., don't worry  *      about it!  *  *      Example:  *  *              a:  [2 3 4 9 10 30]  *              b:  [5 8 8 11 20 40]  *  *              after call on (a,b)  *  *              a:  [2 3 4 5 8 8 9 10 11 20 30 40]  *              b:  []  *   * implementation:  should not allocate ANY new list  *      nodes -- it should just re-link existing  *      nodes.  *  *      Must be linear time in the |a|+|b| -- i.e.,  *      the total number of elements being processed.  */ void lst_merge_sorted(LIST *a, LIST *b){  } 

Explanation / Answer

Hi ,

Implemented code as you said..

let me know if you have any Queries..

CODE:

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

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

void mvNode(struct node** destRef, struct node** sourceRef);

/* Takes two lists sorted in increasing order, and splices their nodes together to make one big sorted list which is returned. */
struct node* lst_merge_sorted(struct node* a, struct node* b)
{
/* a dummy first node to hang the result on */
struct node dummy;

/* tail points to the last result node */
struct node* tail = &dummy;

/* so tail->next is the place to add new nodes
to the result. */
dummy.next = NULL;
while(1)
{
if(a == NULL)
{
/* if either list runs out, use the other list */
tail->next = b;
break;
}
else if (b == NULL)
{
tail->next = a;
break;
}
if (a->data <= b->data)
{
mvNode(&(tail->next), &a);
}
else
{
mvNode(&(tail->next), &b);
}
tail = tail->next;
}
return(dummy.next);
}

/* UTILITY FUNCTIONS */
/*mvNode() function takes the node from the front of the source, and move it to the front of the dest.
It is an error to call this with the source list empty.

Before calling mvNode():
source == {1, 2, 3}
dest == {1, 2, 3}

Affter calling mvNode():
source == {2, 3}
dest == {1, 1, 2, 3}
*/
void mvNode(struct node** destRef, struct node** sourceRef)
{
/* the front source node */
struct node* newNode = *sourceRef;
assert(newNode != NULL);

/* Advance the source pointer */
*sourceRef = newNode->next;

/* Link the old dest off the new node */
newNode->next = *destRef;

/* Move dest to point to the new node */
*destRef = newNode;
}

/* Function to insert a node at the beginging of the linked list */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);   

/* move the head to point to the new node */
(*head_ref) = new_node;
}

/* Function to print nodes in a given linked list */
void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

/* Drier program to test above functions*/
int main()
{
struct node* rst = NULL;
struct node* a = NULL;
struct node* b = NULL;

/*add elements to the list 1*/

push(&a, 15);
push(&a, 10);
push(&a, 5);
  
  
/*add elements to the list 2.*/
push(&b, 20);
push(&b, 3);
push(&b, 2);

/*calling function to merge both*/
rst = lst_merge_sorted(a, b);

printf(" Merged Linked List is: ");
printList(rst);

getchar();
return 0;
}

Sample Output:

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects