Intersection of Linked Lists

In some cases 2 linked list can intersect each other. In the following diagram, you see that 2 NULL terminated singly linked lists are intersected at the node 5.

In this implementation, we will find in which node the 2 lists are intersecting each other. The function will return the node address. We will use the helper functions form the previous post which add nodes to the lists, print the lists etc...

Function which finds the intersection:

/*
 * link_list_intersect()
 *  Finds the intersection node of 2 lists.
 */
struct node *link_list_intersect(struct node *list1, struct node *list2)
{
    struct node *long_list;
    struct node *short_list;
    int diff = 0;

    /*
     * Get the lengths of the lists.
     */
    int len1 = list_lenght_get(list1);
    int len2 = list_lenght_get(list2);

    /*
     * Find which list is long and which list is short
     * and find the absolute lenght difference.
     */
    if (len1 >= len2) {
        diff = len1 - len2;
        long_list = list1;
        short_list = list2;
    } else {
        diff = len2 - len1;
        long_list = list2;
        short_list = list1;
    }

    /*
     * Move the long list with the amount of diff. 
     */
    if (diff) {
        while (diff--) {
            long_list = long_list->next;
        }
    }

    /*
     * Compare the nodes of the list.
     */
    while (len1--) {
        if (long_list == short_list) {
            /*
             * nodes are equal return the long one (doesn't matter).)
             */
            return long_list;
        }
        /*
         * Move the lists, nodes are not equal in this iteration.
         */
        long_list = long_list->next;
        short_list = short_list->next;
    }

    /*
     * There is no intersection point.
     */
    return NULL;
}

Test Code:

/*
 * Global list objects.
 */
struct node *list1 = NULL; 
struct node *list2 = NULL;

int main(void)
{
    struct node *n[20];
    unsigned int i;

    for (i = 0; i < 20; i++) {
        n[i] = node_create(i);
        if (!n[i]) {
            // Free the previous ones.
            return -1;
        }
    }   

    list_add_node_tail(&list1, n[0]);
    list_add_node_tail(&list1, n[1]);
    list_add_node_tail(&list1, n[2]);
    list_add_node_tail(&list1, n[3]);
    list_add_node_tail(&list1, n[4]);
    list_add_node_tail(&list1, n[12]);
    list_add_node_tail(&list1, n[13]);
    list_add_node_tail(&list1, n[14]);
    list_add_node_tail(&list1, n[15]);
    list_add_node_tail(&list1, n[16]);
    list_add_node_tail(&list1, n[17]);
    list_add_node_tail(&list1, n[18]);
    list_add_node_tail(&list1, n[19]);

    list_add_node_tail(&list2, n[5]);
    list_add_node_tail(&list2, n[6]);
    list_add_node_tail(&list2, n[7]);
    list_add_node_tail(&list2, n[8]);
    list_add_node_tail(&list2, n[9]);
    list_add_node_tail(&list2, n[10]);
    list_add_node_tail(&list2, n[11]);
    list_add_node_tail(&list2, n[12]);

    printf("List 1:\n");
    list_print(list1);
    printf("\nList 2:\n");
    list_print(list2);

    struct node *nd = link_list_intersect(list1, list2);
    if (nd) {
        printf("\nIntersection node is: %p data: %d\n", nd, nd->data);
    } else {
        printf("\nThere is no intersect\n");
    }

    return 0;
}

Test Output:

List 1:

0->1->2->3->4->12->13->14->15->16->17->18->19->NULL

List 2:

5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->NULL

Intersection node is: 0x7fee9b402780 data: 12


Source Download:

https://github.com/sezginmurat/list_lib.git