有序链表的合并

前言

看了网上人家写的，自己拿来用一用，效果不如意，有的管都不管直接将链表2接在链表1之后，有的虽然有比较一下链表1与2的元素大小，在进行链接，但运行后有bug。自己写了一下，大概就两种策略：

• 需要第三方

  这种比较好理解，就是从链表1与2中依次拿过来重新组织。

  void MergerList(PNODE &LA,PNODE &LB,PNODE &LC){
  	OutputStudent(LA);
  	OutputStudent(LB);
  	
  	NODE *pa,*pb,*pc;		// pa指向LA,pb指向LB,pc指向LC;
  	pa=LA->next;
  	pb=LB->next;
  	LC=LA;
  	pc=LC;						//pc指向LC头指针 
  	while(pa&&pb){
  		if(pa->data<=pb->data){
  			pc->next=pa;
  			pc=pa;				//更新pc的指向 
  			pa=pa->next;
  		}
  		else{
  			pc->next=pb;
  			pc=pb;
  			pb=pb->next;
  		}
  	}
  	pc->next=pa?pa:pb;
  	delete LB;
  }

  运行结果：

  

• 将链表2插在链表1合适位置

  这个网上大多数也是让下面q指向A链表第一个结点，调试时你会发现如果B第一个结点比A的小，此时q又指着A的第一个结点，B怎么插在A前面。
  所以这里A链表只要头结点，然后依次将B插进来。

  PNODE GuiblingList(PNODE A,PNODE B){
  	OutputStudent(A);
  	OutputStudent(B);
  	
  	NODE *p,*q,*r;		// p指向A,q指向B;
  	q=A;
  	p=B->next;
  		
  	while(p){		
  		while((q->next)&&(q->next->data<p->data)){
  			q=q->next;
  		}
  
  		r=p;
  		p=p->next;
  		r->next=q->next;
  		q->next=r;		
  	}
  	return A;
  }

  运行结果：

  

  总的代码：

#include<iostream> 
#include <stdlib.h>
#include <string.h>
using namespace std;

typedef struct Node//结点
{
	int data;//数据域
	struct Node *next;//指针域
}NODE, *PNODE;//NODE等价于struct Student st||PNODE等价于struct Node *next

PNODE InputStudent(void)
{
	int len;//学生的人数
	NODE stu;
	PNODE pHead = (PNODE)malloc(sizeof(NODE));//定义一个头结点并且为头结点分配内存
	if(NULL == pHead)	//判断内存是否为空
	{
		printf("内存分配失败,程序终止!\n");
		exit(-1);
	}
	PNODE pTail = pHead;//定义一个指向头结点的指针
	pTail->next = NULL;//清空指针域
	printf("请输入个数:");
	scanf("%d",&len);
	for(int i=0; i<len; i++)
	{
		printf("请输入第%d个:\n", i+1);
		cin>>stu.data;

		PNODE pNew = (PNODE)malloc(sizeof(NODE));	//为新节点分配内存
		if(NULL == pNew)	//判断内存是否为空
		{
			printf("内存分配失败,程序终止!\n");
			exit(-1);
		}

		pNew->data = stu.data;//初始化结点的数据域	
		pTail->next = pNew;//将新结点挂到老结点后
		pNew->next = NULL;//清空新结点的指针域
		pTail = pNew;//将pTail移到新结点上
	}
	return pHead;
}

void OutputStudent(PNODE pHead)//输出学生信息
{
	PNODE p = pHead->next;//定义一个指针用于遍历学生信息
	printf("\n数据如下:\n");	
	while(NULL != p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
}

void MergerList(PNODE &LA,PNODE &LB,PNODE &LC){
	OutputStudent(LA);
	OutputStudent(LB);
	
	NODE *pa,*pb,*pc;		// pa指向LA,pb指向LB,pc指向LC;
	pa=LA->next;
	pb=LB->next;
	LC=LA;
	pc=LC;						//pc指向LC头指针 
	while(pa&&pb){
		if(pa->data<=pb->data){
			pc->next=pa;
			pc=pa;				//更新pc的指向 
			pa=pa->next;
		}
		else{
			pc->next=pb;
			pc=pb;
			pb=pb->next;
		}
	}
	pc->next=pa?pa:pb;
	delete LB;
}

PNODE GuiblingList(PNODE A,PNODE B){
	OutputStudent(A);
	OutputStudent(B);
	
	NODE *p,*q,*r;		// p指向A,q指向B;
	q=A;
	p=B->next;
		
	while(p){		
		while((q->next)&&(q->next->data<p->data)){
			q=q->next;
		}

		r=p;
		p=p->next;
		r->next=q->next;
		q->next=r;		
	}
	return A;
}

int main(){
	PNODE LA= InputStudent();
	PNODE LB= InputStudent();
	PNODE LC;
	
	LC=GuiblingList(LA,LB);
	OutputStudent(LC);
	
//	MergerList(LA,LB,LC);
//	OutputStudent(LC);
	
	return 0;
}