Wednesday, October 10, 2012

Intersection of two lists

Given two lists sorted in increasing order, create and return a new list representing the intersection of the two lists. The new list should be made with its own memory — the original lists should not be changed.

/*
 * Insert an element in linked list
 */
void Insert(nodeptr* head, int data) {
     nodeptr newNode = (nodeptr) malloc(sizeof(struct node));
     if(newNode == NULL)
                return;
     newNode->data = data;
     newNode->next = *head;
     *head = newNode;
}
/*
 * Compute a new sorted list that represents the intersection
 * of the two given sorted lists.
 */
nodeptr SortedIntersect(nodeptr a, nodeptr b)
{
    nodeptr newList = NULL,temp;
    if(a == NULL || b == NULL) return NULL;
    else {
        while(a != NULL) {
            temp = b;
            while(temp != NULL && a->data < temp->data)
                temp = temp->next; 
            if(temp != NULL) {
                if(a->data == temp->data){
                    Insert(&newList, a->data);
                }
            }
            a = a->next;
        }
        return newList;
    }
}

No comments:

Post a Comment