在交替位置合并两个链表

Question

我正在合并两个链表，第三个链表由交替位置的元素组成，但合并的函数不起作用

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;
    }
}

Answer 1

假设我们要在第二个列表中交替添加节点。所以第二个列表将成为新列表。思路是

保留2个指向当前节点的指针。最初原始列表 p 和 q.
While they are not null (both are not null) you store in the next address of the both nodes.
现在你要做什么？您将指向 p 的下一个到 q 的当前和 q 的当前到 p 的下一个。
当前指针现在将正确更改为下一个节点，因为它们现在将被处理。

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

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

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

代码将是这样的（有关更多信息，请查看 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
}

创建第三个链表作为结果

你可以像以前那样做。现在您需要进行哪些更改？
简单地说，你可以复制list A和list B，然后将它们作为参数传递给列表，你将从前面显示的函数中得到第三个列表以上。
但这是一个非常原始的解决方案。您还可以在函数中以线性时间动态构建列表。

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.

Answer 2

试试这个：

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;
}

或者这个（更少的代码，更多的时间）：

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;
}

Answer 3

由于没有声明所涉及的类型，没有关于您的列表如何初始化的信息，也没有关于您如何尝试输出结果的详细信息，我只能笼统地说。鉴于您确实说过要避免修改原始列表，但是可以肯定的是，您需要对每个列表中的每个节点进行 copy。这是您可以做到的一种方法：

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;
}

基本思想是同时遍历两个输入列表，或者将节点从一个输入和另一个输入复制到输出列表中。此特定实现 returns 合并列表中节点总数的计数，或 -1 出错；合并列表的头部通过第三个参数返回。如果输入列表具有不同的长度（较长列表中的剩余节点附加在末尾），或者如果一个或两个输入列表为空，它不会被绊倒。复制节点的大部分细节都分解到了 COPY() 宏中。 dummy 节点避免合并列表的头部成为特例。

无论如何，如果构建三个列表的节点类型不同，则执行任何操作都没有意义。

在交替位置合并两个链表

Merging two linked lists at alternate position

c

linked-list

data-structures

创建第三个链表作为结果