Mixing the elements of 2 lists (problem on returning to a list)

**IrfanMokhtar** · 06-24-2018

Code:

struct NODE
{
    int x;
    char c;
    struct NODE *next;
};

I have a data structure named NODE, which then I used to create a list that
has 20 elements in it.

Code:

void make_list(struct NODE **n)
{
    for(int k = 0; k < 20; k++)
    {
        *n = (struct NODE *)malloc(sizeof(struct NODE));
        (*n)->x = k+1;
        (*n)->c = 'A'+k;
        n = &(*n)->next;
    }
    *n = NULL;
}

Then I divide the list into 2 new list.

Code:

void divide_list(struct NODE *n, struct NODE **n1, struct NODE **n2)
{
    struct NODE *node;
    int i, j;
    i = 1; j = 1;
    node = n;
    while(node != NULL)
    {
        node = node->next;
        i++;
    }
    node = n;
    while(j<i/2)
    {
        node = node->next;
        j++;
    }
    *n2 = node->next;
    node->next = NULL;
    *n1 = n;
}

But now the problem that I am facing is how to mix the elements of 2 list,
which the elements of n2 will alternating with every n1 elements.
I tried to do this program. It succeeded but how to make it become into a
new head address which just can call the list once without repeating just
like how I am doing right now. Is there any other way to do the alternating?

Code:

void mix_list(struct NODE *n1, struct NODE *n2)
{
    int k;
    k = 0;
    struct NODE *n_tmp, *n_tmp1;

    n_tmp = n1;
    n1 = n1->next;

    printf("[%d]:x = %d, c = %c\n", k++, n_tmp->x, n_tmp->c);

    n_tmp = n_tmp->next;
    n_tmp = n2;
    n2 = n2->next;

    printf("[%d]:x = %d, c = %c\n", k++, n_tmp->x, n_tmp->c);
    while(n1 != NULL && n2 != NULL)
    {
        n_tmp = n_tmp->next;
        n_tmp = n1;
        n1 = n1->next;

        printf("[%d]:x = %d, c = %c\n", k++, n_tmp->x, n_tmp->c);

        n_tmp = n_tmp->next;
        n_tmp = n2;
        n2 = n2->next;

        printf("[%d]:x = %d, c = %c\n", k++, n_tmp->x, n_tmp->c);
    }

    while(n_tmp != NULL)
    {
        printf("[%d]:x = %d, c = %c\n", k++, n_tmp->x, n_tmp->c);
        n_tmp = n_tmp->next;
    }
    printf("\n");
}

P/S: Sorry for my bad English.

**whiteflags** · 06-24-2018

There are a couple of problems with your current attempt. The first is that if n_tmp is the head of the new list, then the new list is thrown away once the function is done, because n_tmp is a local variable. You could make a return statement or assign the new head to a parameter (like you did for make_list), but I think there is an even easier way.

The next problem with your attempt is there is nothing in the function to handle what I would think is a common case: when one list is longer than the other.

If I understand the problem right, then the answer would be a function like this.

Code:

void mix_list (struct NODE *n1, struct NODE *n2)
{
   if (n1 == NULL || n2 == NULL) return;

   struct NODE *next = NULL;
   while (n1 != NULL && n2 != NULL) {
      next = n2->next;
      n2->next = n1->next;
      n1->next = n2;

      n1 = n1->next->next; // skip a node
      n2 = next;
   }

   if (n2 != NULL) {
      n1 = n2;
   }
}

All this does is interleave nodes of n2 into n1. If n1 is shorter than n2, the rest of n2 is added to the end of n1. This makes n1 the head of your new list, and n2 is invalid. If you want n1 and n2 to be valid lists afterwards, then something like your current attempt is more appropriate.

Thread: Mixing the elements of 2 lists (problem on returning to a list)

Thread Tools

Search Thread

Display

Mixing the elements of 2 lists (problem on returning to a list)

Similar Threads

Printing a list which has elements other lists (same struct) recursively.

Creating a list with elements other lists (same struct)

Don't Understand Outputting Linked Lists Elements

Linked lists; getting the current elements next element

explain linked lists returning a node address

Tags for this Thread