Question

5．不使用额外空间,将 A,B两链表的元素交叉归并

Answer 1

#include <iostream>
using namespace std;

struct node
{
int val;
node* next;
};

node* creat(int n)
{
node* head;
node* p1;
node* p2;
for (int i=0; i<n; i++)
{
if (i == 0)
{
head = new node;
cout<<"请输入第1个元素：";
cin>>head->val;
head->next = NULL;
p1 = head;
}
else
{
p2 = new node;
cout<<"请输入第"<<i+1<<"个元素：";
cin>>p2->val;
p2->next = NULL;
p1->next = p2;
p1 = p2;
}
}
return head;
}

void merge(node* headA,node* headB) //注意：链表A的长度要大于等于链表B
{
if (headA == NULL || headB == NULL)
{
return;
}
merge(headA->next,headB->next);
headB->next = headA->next;
headA->next = headB;
}

int main()
{
node* headA;
node* headB;
node* p;
cout<<"链表A: \n";
headA = creat(6);
cout<<"链表B: \n";
headB = creat(3);
p = headA;
merge(headA,headB);
cout<<"合并后的链表为：\n";
while (p != NULL)
{
cout<<p->val;
p = p->next;
}
return 0;
}
运行正确！

Answer 2

using namespace std;

struct node
{
int val;
node* next;
};

node* creat(int n)
{
node* head;
node* p1;
node* p2;
for (int i=0; i<n; i++)
{
if (i == 0)
{
head = new node;
cout<<"请输入第1个元素：";
cin>>head->val;
head->next = NULL;
p1 = head;
}
else
{
p2 = new node;
cout<<"请输入第"<<i+1<<"个元素：";
cin>>p2->val;
p2->next = NULL;
p1->next = p2;
p1 = p2;
}
}
return head;
}

void merge(node* headA,node* headB) //注意：链表A的长度要大于等于链表B
{
if (headA == NULL || headB == NULL)
{
return;
}
merge(headA->next,headB->next);
headB->next = headA->next;
headA->next = headB;
}

int main()
{
node* headA;
node* headB;
node* p;
cout<<"链表A: \n";
headA = creat(6);
cout<<"链表B: \n";
headB = creat(3);
p = headA;
merge(headA,headB);
cout<<"合并后的链表为：\n";
while (p != NULL)
{
cout<<p->val;
p = p->next;
}
return 0;
}
运行正确！

Answer 3

friend void Merge(LinkList &L1,LinkList &L2)
{
p1 = L1.head->next;
p2 = L2.head->next;
p3 = L1.head;
while((p1 != NULL) && (p2 != NULL))
{
p3->next = p1;
p1 = p1->next;
p3 = p3->next;
p3->next = p2;
p2 = p2->next;
p3 = p3->next;
}
if(p1 != NULL) p3->next = p1;
if(p2 != NULL) p3->next = p2;
delete L2.head;
L2.head = NULL;
}

追问

你的p3从哪来的，能不能讲的清楚一点，p1,p2,p3含义，以及思路？

追答

p1指向A链表的第一个结点 p2指向B链表的第一个结点 p3指向A链表的头指针