合并两个有序链表_如何合并两个有序链表c++,不额外占据空间

将两个有序链表（a、b）合并为一个有序链表（c），不使用额外的空间

令 c 链表的头指针 Pc 指向 a 链表的头，Pa、Pb 分别指向 a、b 链表的第一个结点

从a、b链表的第一个元素开始比较，Pc 始终指向 c 链表的最后一个元素

void  MergeList_L(LinkList La,LinkList Lb,LinkList &Lc)
{
   LinkList pa,pb,pc;
   Lc=La;
   pc=Lc;
   pa=La->next;
   pb=Lb->next;
   while(pa!=NULL && pb!=NULL)
   {
        if(pa->data > pb->data)
        {
            pc->next=pa;
            pc=pc->next;
            pa=pa->next;
        }
  		else
        {
            pc->next=pb;
            pc=pc->next;
            pb=pb->next;
        }
   }
  
   if(pa!=NULL)
   {
  	   pc->next=pa;
   }
   else
   {
       pc->next=pb;
   }
   free(Lb);
} 	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

若直接使用原序列中的结点，返回归并后的带头结点的链表头指针。

List Merge( List L1, List L2 )
{
    List L3=(struct Node *)malloc(sizeof(struct Node));
    List L=L3;
    List p=L1->Next;
    List q=L2->Next;
    while (p && q)
    {
        if (p->Data < q->Data)
        {
            L->Next=p;
            p=p->Next;
            L=L->Next;
        }
        else
        {
            L->Next=q;
            q=q->Next;
            L=L->Next;
        }       
    }

    if (p) L->Next=p;
    if (q) L->Next=q;
    L1->Next=NULL;
    L2->Next=NULL;
    return L3;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28