C语言 将两个已排序（从小到大）的线性表归并为一个线性表，并且归并后的线性表仍然按照从小到大的顺序

Question

将两个已排序（从小到大）的线性表归并为一个线性表，并且归并后的线性表仍然按照从小到大的顺序排序。

Answer 1

以下代码创建了一个奇数线性表和一个偶数线性表，奇数表有10个节点，偶数表有5个节点。

先看运行结果

以下是代码

#include <stdio.h>
#include <stdlib.h>
typedef struct List {
 int number;
 struct List*next;
} LinearList;
LinearList*createList(int);
LinearList*createList2(int);
void freeList(LinearList*);
LinearList* merger(LinearList*,LinearList*);
void printList(LinearList*);
main() {
 LinearList*list1Head=createList(10);
 printf("线性表一：\n");
 printList(list1Head);
 printf("\n");
 LinearList*list2Head=createList2(5);
 printf("线性表二：\n");
 printList(list2Head);
 printf("\n");
 LinearList*head=merger(list1Head,list2Head);
 printf("归并后的线性表：\n");
 printList(head);
 freeList(list1Head);
 freeList(list2Head);
}
LinearList* merger(LinearList*list1Head,LinearList*list2Head) { //将list2分解插入list1
 LinearList*node1=list1Head->next,*node2=list2Head->next;
 LinearList*preNode1=list1Head,*preNode2=list2Head;
 while(node1!=NULL&&node2!=NULL) {
  if(node1->number>=node2->number) { //node2放在node1前面
   //先从list2中删除node2
   preNode2->next=node2->next;
   //下面两行把node2插入list1
   preNode1->next=node2;
   node2->next=node1;
   //移动指针
   preNode1=node1;
   node1=node1->next;
   node2=preNode2->next;
  } else { //node2放在node1后面
   //先从list2中删除node2
   preNode2->next=node2->next;
   //下面两行把node2插入list1
   node2->next=node1->next;
   node1->next=node2;
   //移动指针
   preNode1=node2;
   node1=node2->next;
   node2=preNode2->next;
  }
 }
 return list1Head;
}
LinearList*createList(int n) {
 LinearList*head=NULL,*end=NULL,*node=NULL;
 end=head=(LinearList*)malloc(sizeof(LinearList));
 int i;
 for(i=1; i<=n; i++) {
  node=(LinearList*)malloc(sizeof(LinearList));
  node->number=i*2-1;//奇数
  end->next=node;
  end=node;
 }
 end->next=NULL;
 return head;
}
LinearList*createList2(int n) {
 LinearList*head=NULL,*end=NULL,*node=NULL;
 end=head=(LinearList*)malloc(sizeof(LinearList));
 int i;
 for(i=1; i<=n; i++) {
  node=(LinearList*)malloc(sizeof(LinearList));
  node->number=i*2;//偶数
  end->next=node;
  end=node;
 }
 end->next=NULL;
 return head;
}
void freeList(LinearList*head) {
 LinearList*node=head;
 while(head!=NULL) {
  head=head->next;
  free(node);
  node=head;
 }
}
void printList(LinearList*head) {
 LinearList*node=head->next;
 while(node!=NULL) {
  printf("%d ",node->number);
  node=node->next;
 }
 printf("\n");
}

Answer 2

两种办法：
1、直接将一个链表尾节点指针指向另一个链表首节点，再遍历新链表，冒泡排序。
2、两个都是排序好的，那么就不需要合并后再排序了。
只要同时遍历两个链表(都是从小的节点开始取) ，每次比较两个节点，然后取最小的那个节点，把它从原链表中断开，放在一边，再重新遍历两个链表，再比较两节点，依次内推，直到取完所有节点。
将依次取出节点连成新链表，就是题目要的(可以重新定义一个链表头指针指向第一个取出的节点，后面取出的节点连上去就行) 。