Question

将两个单链表合并为一个单链表

将两个单链表合并为一个单链表
L1=(x1,x2,````xn),L2=(y1,y2,```,ym)
它们是两个是线性表，采用带头结点的单链表存储，设计一个算法合并L1,L2，结果放在线性表L3中。
要求如下：
L3=(x1,y1,x2,y2,````,xm,ym,xm+1,```,xn) m<=n
L3=(x1,y1,x2,y2,```,xn,yn,yn+1,```,ym) m>n
L3仍采用单链表存储，算法的空间复杂度为为O(l)。

Answer 1

对应这个问题的算法：
void MergeList(LinkList La, LinkList &Lb, LinkList &Lc) 
{ 
  
  LinkList pa=La->next,pb=Lb->next,pc;
  Lc=pc=La; 
  while(pa && pb) 
    if(pa->data<=pb->data) 
    { pc->next=pa; 
      pc=pa; 
      pa=pa->next; 
    }
    else 
    { pc->next=pb; 
      pc=pb; 
      pb=pb->next; 
    }
  pc->next=pa ? pa : pb; 
  free(Lb); 
  Lb=NULL; 
}
需要全部程序的话私信我

Answer 2

typedef int ElementType;
typedef struct table
{
    ElementType data;
    struct table *next;
}List, Node;

void MergeList(List *L1, List *L2, List *L3)
{
    List *p = L1->next;
    List *q = L2->next;
    List *s = L3;
    
    while(p!=NULL && q!=NULL)
    {
        s->next = p;
        s = s->next;
        p = p->next;
        
        s->next = q;
        s = s->next;
        q = q->next;
    }
    s->next = (p!=NULL) ? p:q;
}