C 合并两个链表

Question

我正在尝试将两个链表的内容复制到一个链表中，以便一次复制一个元素（从每个链表）。

所以，如果我有：list1 = [1,2,3]，list2 = [4,5,6]，result = [1,4,2,5,3,6].如果一个列表比另一个列表短，则其余节点将追加在结果列表的末尾。

这是我的代码，它有一个轻微的错误：它在最后创建一个额外的节点（我不想要）。

node *list_copy(node *list1, node *list2) 
{
    node *mylist = newnode(); 
    node *head = mylist;
    while (list1 != NULL || list2 != NULL) {        
        if (list1 != NULL) {
            mylist->data = list1->data;
            mylist->next = newnode();
            mylist = mylist->next;
        
            list1 = list1->next;
        } 
        if (list2 != NULL) { 
            mylist->data = list2->data;
                mylist->next = newnode();
            mylist = mylist->next;
            list2 = list2->next;
        }
    }
    return head;
}   

如何修改它，使其不创建最后一个节点？

示例输入：

List1 = [1,2,3], List2 = [1,2,3,4,5,6], Result = [1,1,2,2,3,3,4,5,6,0]; 

Answer 1

不要在

一次 while 块中进行合并，这会使您的代码更难阅读。在功能上将列表副本分解为另一个函数并调用它两次。

您在循环之前执行一个新节点，然后在添加当前项后执行新节点。怎么样...

node *mylist; 
node *head;
while (listItem != null) {
    if(head == null) {        
       mylist = newnode();
       head = myList;
    }
    else {
       mylist->next = newnode();
       mylist = mylist->next;
    }

    mylist->data = listItem->data;    
    listItem = listItem->next;
}

Answer 2

这应该让你开始。请注意，在您的示例中，输出似乎需要排序。您可以通过添加一些额外的测试将其作为列表合并操作的一部分来处理，但我会将其保留为练习（不确定排序结果是否是您要求的一部分）。

#include <iostream>
#include <fstream>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <cmath>
#include <complex>
#include <stack>
using namespace std;
struct node {
  int data;
  node* next;
};
node *list_copy(node *list1, node *list2) 
{
    node *mylist;
    node *head;
    mylist = NULL;
    while (list1 != NULL || list2 != NULL) {        
        if (mylist == NULL) {
            mylist = new node;
            head = mylist;
        }
        else {
            mylist->next = new node;
            mylist = mylist->next;
        }
        if (list1 != NULL) {
            mylist->data = list1->data;
            list1 = list1->next;
        } 
        else if (list2 != NULL) { 
            mylist->data = list2->data;
            list2 = list2->next;
        }
    }
    return head;
}   
node* addnode(node* list, int val) {
  if (list == NULL)
    list = new node;
  else {
    list->next = new node;
    list = list->next;
  }
  list->data = val;
  return list;
}
int main() {
  node* list1;
  node* head1;
  node* list2;
  node* head2;
  list1 = NULL;
  list2 = NULL;
  list1 = addnode(list1,1);
  head1 = list1;
  list1 = addnode(list1,2);
  list1 = addnode(list1,3);
  list2 = addnode(list2,1);
  head2 = list2;
  list2 = addnode(list2,2);
  list2 = addnode(list2,3);
  list2 = addnode(list2,4);
  list2 = addnode(list2,5);
  list2 = addnode(list2,6);
  node* m = list_copy(head1,head2);
  while(m != NULL) {
    cout<<(m->data)<<endl;
    m = m->next;
  }
  return 0;
}

输出：

---------- Capture Output ----------
> "c:windowssystem32cmd.exe" /c C:temptemp.exe
1
2
3
1
2
3
4
5
6
> Terminated with exit code 0.

Answer 3

下面是您的代码，只需稍作修改。希望这对您有所帮助

node *list_copy(node *list1, node *list2) 
{
    node *mylist = NULL; 
    node *head = NULL;
    while (list1 != NULL || list2 != NULL) {        
        if (head == NULL)
        {
            mylist = newnode();
            head = mylist;
        }  
        else
        {
            mylist->next = newnode();
            mylist = mylist->next;                 
        } 
        if (list1 != NULL) {
            mylist->data = list1->data;   
            list1 = list1->next;
        } 
        if (list2 != NULL) { 
            mylist->data = list2->data;
            list2 = list2->next;
        }
        mylist->next = NULL;
    }
    return head;
}

Answer 4

更新：OP 似乎想要列表的副本。

#include <stdlib.h>
struct llist * llist_merge_and_dup(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r) );
struct llist *llist_dup(struct llist *org);
struct llist *llist_dup(struct llist *org)
{
struct llist *new;
new = malloc (sizeof *new);
if (!new) return NULL;
memcpy (new, org, sizeof new);
new->next = NULL;
return new;
}
struct llist * llist_merge_and_dup(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *result, **tail;
for (result=NULL, tail = &result; one && two; tail = &(*tail)->next ) {
        if (cmp(one,two) <=0) { *tail = llist_dup(one); one=one->next; }
        else { *tail = llist_dup(two); two=two->next; }
        }
for( ; one; one = one->next) {
        *tail = llist_dup(one);
        }
for( ; two; two = two->next) {
        *tail = llist_dup(two);
        }
return result;
                                                                                              }