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

  1. #1
    Registered User
    Join Date
    Jun 2018
    Posts
    1

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

    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.

  2. #2
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,608
    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.
    Attached Files Attached Files
    • File Type: c foo.c (978 Bytes, 32 views)
    Last edited by whiteflags; 06-24-2018 at 10:49 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 06-18-2018, 11:28 AM
  2. Replies: 3
    Last Post: 06-16-2018, 08:30 AM
  3. Don't Understand Outputting Linked Lists Elements
    By NM Greg in forum C++ Programming
    Replies: 4
    Last Post: 08-20-2017, 01:35 AM
  4. Replies: 22
    Last Post: 10-22-2005, 08:42 AM
  5. explain linked lists returning a node address
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 12-11-2001, 09:53 PM

Tags for this Thread