3.10

4.将两个单链表合并成一个有序单链表
由于以前初学c++时所写的代码不堪入目，不符合规范性，完整性和鲁棒性，于是今日重写其核心算法以警示自己。
Node* Merge(Node p1Head, Node p2Head)
{
	if(p1Head == nullptr)
		return p2Head;
	if(p2Head == nullptr)
		return p1Head;
	
	Node* pMergedHead=nullptr;
	
	if(p1Head->info<p2Head->info)
	{
		pMergedHead=p1Head;
		pMergedHead->next=Merge(p1Head->next,p2Head);
	}
	else
	{
		pMergedHead=p2Head;
		pMergedHead->next=Merge(p1Head,p2Head->next)
	}
	return pMergedHead;
}

思路：因为链表可以由结点轻松构造，所以首先需要创建单链表的元素，然后选择构造方式构造单链表，本代码为后插构造单链表。然后有了链表，怎么合并为一个有序单链表。大体可以先尝试排序构造的每个单链表，然后再在合并的时候进行有序比较排列即可。
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
typedef struct Node {
 
 int info;

 struct Node *next;

}*List;
void creatList(List *head,int n) {

 int i;

 List p,q;

 *head = (List)malloc(sizeof(struct Node));

 (*head)->next = NULL;

 q = *head;

 for ( i = 0; i < n; i++)

 {

  p = (List)malloc(sizeof(struct
Node));

  cin >> p->info;

  p->next = q->next;

  q->next = p;

  p = q;

 }

}
int List_length(List a);

void maopaosort(List p) {

 List la, lb;

 int n = List_length(p);

 int i, j,temp;

 for ( i = 0,la=p->next; i < n;
i++,la=la->next)

 {

  for ( j = i+1,lb=la->next; j
< n; j++,lb=lb->next)

  {

   if
(la->info>lb->info)

   {

    temp
= la->info;

    la->info
= lb->info;

    lb->info
= temp;

   }

  }

 }

}
int List_length(List a) {

 int i=0;

 List p;

 p = a->next;

 while (p != NULL)

 {

  ++i;

  p = p->next;

 }

 return i;

}
void outputlist(List head) {

 List p;

 p = head->next;

 while (p!=NULL)

 {

  cout << p->info
<< " ";

  p=p->next;

 }

}
void merge(List l1, List l2, List *l3) {

 List p1,p2, p3;

 *l3 = l1;

 p1 = l1->next;

 p2 = l2->next;

 p3 = *l3;

 while (p1!=NULL&&p2!=NULL)

 {

  if (p1->info >
p2->info) {

   p3->next=
p2;

   p2 =
p2->next;

   p3 =
p3->next;

  }

  else

  {

   p3->next =
p1;

   p1 =
p1->next;

   p3 =
p3->next;

  }

}  

 if (p1 != NULL) {

  p3->next= p1;

 }

 else

 {

  p3->next= p2;

 }

}
int main() {

 List a, b, c;

 creatList(&a, 5);

 maopaosort(a);

 //outputlist(a);

 creatList(&b, 4);;

 maopaosort(b);

 //outputlist(b);

 merge(a, b, &c);

 //cout << endl;

 outputlist(c);

}

/*链表*/

#include <stdlib.h>
typedef struct node

{

    int data;

    struct node *next;

}*Listlink;
/*后插法创建单链表*/

void hou_create(Listlink *head,int n)

{

    int i;

    Listlink p,q;

    *head=(Listlink )malloc(sizeof(struct node));

    (*head)->next=NULL;/*建立头结点*/

    q=*head;

    for(i=0;i<n;i++)

    {

       p=(Listlink)malloc(sizeof(struct node));

       scanf("%d",&(p->data));
       p->next=q->next;

       q->next=p;

       q=p;

    }
}
/*将两个递增单链表合并为一个递增的单链表*/

void merge(Listlink la,Listlink lb,Listlink *lc)
{

    Listlink pa,pb,pc;

    *lc=la;                        /*合并后的链表头结点使用a链表的*/
    pa=la->next;

    pb=lb->next;

    pc=*lc;
    while(pa!=NULL&&pb!=NULL)

    {

       if(pa->data<pb->data)

       {

          pc->next=pa;

          pa=pa->next;

          pc=pc->next;

       }

       else

       {

          pc->next=pb;

          pb=pb->next;

          pc=pc->next;

       }

    }

    if(pa!=NULL)pc->next=pa;

    else         pc->next=pb;

}
void print_list(Listlink head)

{

     Listlink p;

     p=head->next;

     while(p!=NULL)

     {

       printf(" %d",p->data);

       p=p->next;

     }

}
main()
{
   Listlink la,lb,lc;
   puts("houcha:");

   hou_create(&lb,10);

   puts("houcha:");

   hou_create(&la,10);
   merge(la,lb,&lc);

   print_list(lc);

   getch();


}

单链表的基本操作   包括 ：链表的创建（头插法，尾插法），链表的遍历，两个单调递增的链表合并为一个单调递增的链表，两个单调递增的链表合并为一个单调递减的链表
 
#include <cstdlib>
#include <iostream>
using namespace std;

//定义单链表的接点
typedef struct Node{
        int data;
        struct Node * next;
        }Nodes; 
//将两个单调递增链表合并成一个 单调递增链表
void merge(Node * a,Node * b,Node * &c){
     Node * p=a->next;//永远指向a的最小的接点
     Node * q=b->next; //永远指向b的最小的接点
     Node * r;//永远指向c的最后一个接点
     c=a; //使用a的头结点
     c->next=NULL;
     free(b);//释放b的头结点
     r=c;//当前c的最后一个接点 也是它的第一个接点
     
     while(p!=NULL && q!=NULL){
             if((p->data)>(q->data)){
                  r->next=q; q=q->next;
                  r=r->next;
                  }
             else{
                  r->next=p; p=p->next;
                  r=r->next;
                  }
             } 
      if(p!=NULL) r->next=p;//将a的剩余接点 添加到c的后面 
      if(q!=NULL) r->next=q;//将b的剩余接点 添加到c的后面 
     } 
     
//将两个单调递增的单链表合并成一个  单调递减的单链表
 void mergeDown(Node * a,Node * b,Node * &c){
     Node * p=a->next;//永远指向a的最小的接点
     Node * q=b->next; //永远指向b的最小的接点
     Node * r;//即将插入的接点 
     c=a; //使用a的头结点
     c->next=NULL;
     free(b);//释放b的头结点
     
     while(p!=NULL && q!=NULL){
             if((p->data)>(q->data)){
                  r=q; q=q->next;
                  r->next=c->next;
                  c->next=r; 
                  }
             else{
                  r=p; p=p->next;
                  r->next=c->next;
                  c->next=r;
                  }
             } 
      while(p!=NULL){//将a的剩余接点 添加到c的后面 
                   r=p; p=p->next;
                  r->next=c->next;
                  c->next=r;
                  }
      while(q!=NULL){//将b的剩余接点 添加到c的后面 
                  r=q;q=q->next;
                  r->next=c->next;
                  c->next=r;
                  }
     } 
//创建链表   尾插法 
void createList(Node * &node ,int data[],int length){
     Node * p;//指向最后一个接点 
     Node * q;//指向新创建的接点
     //创建头结点
     node=(Node *)malloc(sizeof(Node));
     node->next=NULL;
     
     p=node; 
     int i;
     for(i=1;i<=length;i++){
             q=(Node *)malloc(sizeof(Node));
             q->data=data[i];
             p->next=q;
             p=q;
           }     
            p->next=NULL;
     } 

//创建链表  头插法
void createListHead(Node * &node ,int data[],int length){
       Node * q;//指向新创建的接点
       
       //创建头结点
     node=(Node *)malloc(sizeof(Node));
     node->next=NULL;
     
      int i;
     for(i=length;i>=1;i--){
             q=(Node *)malloc(sizeof(Node));
             q->data=data[i];
             q->next=node->next;
             node->next=q;
           }     
     } 
 
//遍历单链表
void showList(Node * node){
     Node * p;//指向当前遍历的接点
     if(node!=NULL)
     p=node->next;
     while(p!=NULL){
             printf("%d-->",p->data);
             p=p->next;
             } 
     } 



int main(int argc, char *argv[])
{
    Node * node=NULL;
    Node * node2=NULL;
     Node * node3=NULL;
    int data[11];
     int data2[11];
    int i;
    for(i=1;i<=10;i++){
                  data[i]=i*i  ;         
                      }
    for(i=1;i<=10;i++){
                  data2[i]=i ;         
                      }
    int length=10;
    createList(node ,data,length);
    createListHead(node2 ,data2,length);
    showList(node);
    printf("\n");
    showList(node2);
    printf("\n");
    mergeDown(node,node2,node3); 
    showList(node3);
    
    system("PAUSE");
    return EXIT_SUCCESS;
}



 

如何创建一个带头结点的有序的单链表？
链表在创建的时候就把它创建成有序的会显得专业许多（雾），

而不是先创建无序链表再排序；

拿一道典型例题举个栗子，相信你们都见过这道题；

Problem Description

输入N个无序的整数，建立一个有序链表，链表中的结点按照数值非降序排列，输出该有序链表。

Input

第一行输入整数个数N；

第二行输入N个无序的整数。

Output

依次输出有序链表的结点值。

Sample Input

6

33 6 22 9 44 5

Sample Output

5 6 9 22 33 44

Hint

不得使用数组！

那么思路是什么呢？

我们可以再输入新的结点时逐个进行查找与插入操作，这样建立的就是有序的链表啦
#include<stdio.h>
struct node
{
 int data;
 struct node * next;
};
struct node * sort(struct node * p,int x)
{
 struct node *ph,*pte,*paf;
 ph=p;
 pte = (struct node *)malloc(sizeof(struct node));
 pte->data = x;pte->next = NULL;
 while (p->next)
 {
  paf = p->next;
  if (paf->data >= x)
  {
   pte->next = p->next;
   p->next = pte;
   return ph;
  }
  p = p->next;
 }
 pte->next = p->next;
 p->next = pte;
 return ph;
 //while外表示的是创建第一个结点和最后一个结点时的情况
 //大小排序为p<pte<=paf
}
void list(struct node *p)
{
 p = p->next;
 while (p)
 {
  printf("%d ", p->data);
  p = p->next;
 }
}
int main()
{
 struct node *ph;
 ph = (struct node *)malloc(sizeof(struct node));
 ph->next = NULL;
 int n, i, x;
 scanf("%d", &n);
 for (i = 0;i < n;i++)
 {
  scanf("%d", &x);
  ph = sort(ph, x);
 }
 list(ph);
 getchar();
 getchar();
 return 0;
}

鸣谢这位V家厨(https://www.cnblogs.com/luoxiaoyi/p/9726720.html)