Question

C语言代码出错求解！建立两个单向链表，按交替的顺序轮流从这两个链表中取其成员归并成为一个新的链表

建立两个单向链表，按交替的顺序轮流从这两个链表中取其成员归并成为一个新的链表，如其中一个链表的成员取完，另一个链表的多余成员依次接到新链表的尾部，并把指向新链表的指针作为函数值返回。例如，若两个链表成员分别是{1,4,6,8,30,45}和{5,10,15}，则链接成的新链表是{1,5,4,10,6,15,8,30,45}。

下面是我编的代码，编译没问题，但是运行到connect函数的时候就停止运行了，手工推导和单步调试都没找出问题出在哪，求大神解答！

#include<stdio.h>
#include<stdlib.h>
#define size sizeof(struct num)
typedef struct num member;
struct num
{
int x;
member *next;
};

member *create() //建立链表
{
member *p1,*p2,*head;
p1=p2=(member *)malloc(size);
head=NULL;
int n=0;
printf("Please input the member and input 0 to end\n");
scanf("%d",&p1->x);
while(p1->x!=0)
{
n++;
if(n==1)
head=p1;
else
p2->next=p1;
p2=p1;
p1=(member *)malloc(size);
scanf("%d",&p1->x);
}
p2->next=NULL;
return head;
}

member *connect(member *head1,member *head2) //链接两链表
{
member *p1,*p2,*head;
member *ph1=head1,*ph2=head2;
p1=p2=(member *)malloc(size);
head=NULL;
int n=0;
while(ph1!=NULL||ph2!=NULL) //两链表都被取完结束循环
{
n++;
if(n==1)
head=p1;
else
p2->next=p1;
p2=p1;
if(ph1!=NULL&&ph2!=NULL) //两链表都未取完
if(n%2) //轮流取两链表中的成员
{
p1->x=ph1->x;
ph1=ph1->next;
}
else
{
p1->x=ph2->x;
ph2=ph2->next;
}
else if(ph1->next==NULL) //其中一个链表被取完
{
p1->x=ph2->x;
ph2=ph2->next;
}
else
{
p1->x=ph1->x;
ph1=ph1->next;
}
p1=(member *)malloc(size);
}
p2->next=NULL;
return head;
}

void print(member *ph3) //打印链表
{
do
{
printf("%d ",ph3->x);
ph3=ph3->next;
}while(ph3!=NULL);
printf("\n");
}

int main()
{
member *head1,*head2,*head3;
printf("Create the list 1\n");
head1=create();
printf("\nCreate the list 2\n");
head2=create();
printf("\n--Connect two lists--\n");
head3=connect(head1,head2);
print(head3);
}

Answer 1

使用递归的方法，同时记录每次取出元素的链表，就可以实现这个功能 。具体程序如下：
首先，建立链表的结构体：

1
2
3
4
5

struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

然后，合并链表的主程序：

ListNode *mergeTwoLists(ListNode *l1, ListNode *l2,bool flag)
{
if (l1 == NULL)
return l2;
else if (l2 == NULL)
return l1;
ListNode *Head;
if (flag == true){
flag = false;
Head = new ListNode(l1->val);
Head->next = mergeTwoLists(l1->next, l2,flag);
}
else{
flag = true;
Head = new ListNode(l2->val);
Head->next = mergeTwoLists(l1, l2->next,flag);
}
return Head;
}

最后，测试的程序：

void testcode()
{
int arr1[6] = { 1, 4, 6, 8, 30, 45 };
int arr2[3] = { 5, 10, 15 };
ListNode l1(1);
ListNode *p = &l1;
for (int i = 1; i < 6; i++)
{
p->next = new ListNode(arr1[i]);
p = p->next;
}
ListNode l2(5);
p = &l2;
for (int i = 1; i < 3; i++)
{
p->next = new ListNode(arr2[i]);
p = p->next;
}
bool flag = true;
ListNode *newHead = mergeTwoLists(&l1, &l2, flag);
while (newHead!= NULL)
{
cout << newHead->val << " ";
newHead = newHead->next;
}
cout << endl;
}

追问

你这是复制的吧，我问的是我的程序哪里错了，要知道正确答案我还用的着你复制