Merging two linked lists at alternate position

Question

I am merging two linked lists and third lists consist of elements at alternate postions but function which will merge is not working

void insert2()
{
    //node ptr-pointer of first linked list<br>
    //node1 ptr1-pointer of second list<br>
    //node2 ptr2 -pointer of the merged linked list

    node *ptr=head;
    node1 *ptr1=head1;
    node2 *ptr2=(node2*)malloc(sizeof(node2));
    node *ptr3;

    while(ptr!=NULL&&ptr1!=NULL)
    {
        //Entering the element of first linked list

        ptr2->info=ptr->info;
        if(head2==NULL)
        {
            ptr->next=NULL;
            head=ptr;
        }
        else
        {
            ptr3=head2;
            while(ptr3->next!=NULL)
            {
                ptr3=ptr3->next;
            }
            ptr3->next=ptr2;
            ptr2->next=NULL;
        }
        //Entering the element of second linked list

        ptr2->info=ptr1->info;
        while(ptr3->next!=NULL)
        {
            ptr3=ptr3->next;
        }
        ptr3->next=ptr2;
        ptr2->next=NULL;
    }
}

Input-2 3 5 6 7// list 1 Input- 8 9 10 11 Output should be-2 8 3 9 5 10 7 11 but the function which I have given above is not working — Newbie786, Mar 26 '15 at 17:57
What if the lists are different lengths? There are a number of related questions, some of them listed on the right. [Merging two sorted linked lists](http://stackoverflow.com/questions/2348374/merging-two-sorted-linked-lists) is close to what you're after; your data is not explicitly sorted, so your comparisons are easier. There are other questions which I've not found about simply merging alternate values from two lists. — Jonathan Leffler, Mar 26 '15 at 17:58
You present neither input nor output functions, nor the code that calls the function you did present, so it's pretty hard for us to determine what could be wrong. It's furthermore unclear why you have three distinct node types. — John Bollinger, Mar 26 '15 at 18:35

user2736738 · Accepted Answer · 2015-03-27T02:48:28.713

Suppose we are going to add the nodes alternatively in the second list. So the second list will become the new list. The idea is

Keep 2 pointers pointing to current node. Initially the original lists p and q.
While they are not null (both are not null) you store in the next address of both nodes.
Now what will you do? You will point to the next of p to current of q and current of q to next of p.
The current pointers will now be properly changed to the next nodes because they will now be processed.

 --------             ----------
| p_curr|------------>|        |--------->NULL
|-------|    p_next-->|--------|

 --------             ----------
| q_curr|------------>|        |--------->NULL
|-------|    q_next-->|--------|

 //After an iteration in the while loop.
 --------                ----------
|       |----|       --> |  p_curr| --------->NULL
|-------|  _ |______|    |--------|
          |  | 
 -------- |  |        ----------
|       |_|  |------->| q_curr |--------->NULL
|-------|             |--------|

The code will be something like this (For more information check link)

void merge(struct node *p, struct node **q)
{
     struct node *p_curr = p, *q_curr = *q;
     struct node *p_next, *q_next;

     // While therre are avialable positions in p
     while (p_curr != NULL && q_curr != NULL)
     {
         // Save next pointers
         p_next = p_curr->next;
         q_next = q_curr->next;

         // Make q_curr as next of p_curr
         q_curr->next = p_next;  // Change next pointer of q_curr
         p_curr->next = q_curr;  // Change next pointer of p_curr

         // Update current pointers for next iteration
         p_curr = p_next;
         q_curr = q_next;
    }

    *q = q_curr; // Update head pointer of second list
}

Creating a third linked list as result

You can do it similar to the previous way. Now what are the changes you nees to have?
Simply you can make a copy of list A and list B and then you pass these as parameters to the list and you will get the third list from the previous function shown above.
But that's quite a primitive solution. You can also build the list in linear time on fly in the function.

struct node * getnode()
{
    struct node *temp=(struct node*)malloc(sizeof(struct node));
    if(temp==NULL)
    {
         printf("\n Error in allocation\n");
         exit(0);
    }
    return temp;
 }

 void merge(struct node *p, struct node *q,struct node **n)   
 {
    struct node *p_curr = p, *q_curr = q;
    struct node **store;
    struct node *n1;   
 // While therre are avialable positions in p
 while (p_curr != NULL || q_curr != NULL)
 {

    if (p_curr) 
    {
        if(first)
        {
             store=&n1;first=0;
        }
        n1=getnode();
        n1->info=p_curr->info;
        n1->next = p_curr->next;
        n1=n1->next;
        p_curr=p_curr->next;
    }
    if (q_curr) 
    {
        if(first)
        {
             store=&n1;first=0;
        }
        n1=getnode();
        n1->info=q_curr->info;
        n1->next = q_curr->next;
        n1=n1->next;
        q_curr=q_curr->next;
     }
  }
  *n=*store;
 }

Remember in this case the two if statements are checking whether any of them is NULL. If it is the case then add the nodes of other list in the resulting node. store stores the address of the first node. After all we need to point to the head of the third node.

actually I am trying to make a third list with alternate nodes and I am not modifying the existing lists — Newbie786, Mar 26 '15 at 18:34

rcgldr · Answer 2 · 2015-03-26T19:25:23.383

Try this:

NODE * AlternateListMerge(NODE *pSrc1, NODE *pSrc2)
{
NODE *pDst = NULL;                      /* destination head ptr */
NODE **ppDst = &pDst;                   /* ptr to head or prev->next */
NODE *pNode;                            /* ptr to node */
    while(pSrc1 || pSrc2){
        if(pSrc1){
            pNode = malloc(sizeof(NODE));
            pNode->info = pSrc1->info;
            pSrc1 = pSrc1->next;
            *ppDst = pNode;
            ppDst = &pNode->next;
        }
        if(pSrc2){
            pNode = malloc(sizeof(NODE));
            pNode->info = pSrc2->info;
            pSrc2 = pSrc2->next;
            *ppDst = pNode;
            ppDst = &pNode->next;
        }
    }
    *ppDst = NULL;
    return pDst;
}

or this (less code, a bit more time):

NODE * AlternateListMerge(NODE *pSrc1, NODE *pSrc2)
{
NODE *pDst = NULL;                      /* destination head ptr */
NODE **ppDst = &pDst;                   /* ptr to head or prev->next */
NODE *pNode;                            /* ptr to node */
NODE *pSwap;                            /* used for swap */
    while(pSrc1 || pSrc2){
        if(pSrc1){
            pNode = malloc(sizeof(NODE));
            pNode->info = pSrc1->info;
            pSrc1 = pSrc1->next;
            *ppDst = pNode;
            ppDst = &pNode->next;
        }
        pSwap = pSrc1;
        pSrc1 = pSrc2;
        pSrc2 = pSwap;
    }
    *ppDst = NULL;
    return pDst;
}

John Bollinger · Answer 3 · 2015-03-26T19:34:02.910

With no declarations of the types involved, no information about how your lists are initialized, and no details about how you are trying to output the result, I can speak only in generalities. Given that you did say you want to avoid modifying the original lists, however, it is certain that you need to make a copy of each node in each list. Here's one way you could do it:

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

#define COPY(from, to, error_label) do { \
    to = malloc(sizeof(struct node));    \
    if (! to) {                          \
        /* allocation error */           \
        goto error_label;                \
    }                                    \
    to->data = from->data;               \
    to->next = NULL;                     \
} while (0)

int merge(struct node *head1, struct node *head2, struct node **result) {
    struct node dummy = { NULL, NULL };
    struct node *merge_tail = dummy;
    int node_count = 0;

    while (head1 || head2) {
        if (head1) {
            COPY(head1, merge_tail->next, allocation_error);
            head1 = head1->next;
            merge_tail = merge_tail->next;
            node_count += 1;
        }
        if (head2) {
            COPY(head2, merge_tail->next, allocation_error);
            head2 = head2->next;
            merge_tail = merge_tail->next;
            node_count += 1;
        }
    }
    *result = dummy->next;
    return node_count;

    allocation_error:
    while (dummy->next) {
        struct node *temp = dummy->next;

        dummy->next = dummy->next->next;
        free(temp);
    }

    return -1;
}

The basic idea is that you walk both input lists at the same time, alternatively copying nodes into the output list from one input and from the other. This particular implementation returns a count of the total number of nodes in the merged list, or -1 on error; the head of the merged list is returned via the third argument. It will not be tripped up if the input lists have different lengths (left over nodes from the longer list are appended at the end), or if either or both input lists are empty. Most of the gory details of copying a node are factored out into the COPY() macro. The dummy node avoids the head of the merged list being a special case.

Any way around, it makes no sense to do any of this if the nodes from which the three lists are built are of different types.

Merging two linked lists at alternate position

3 Answers3

Creating a third linked list as result