3-3.cpp

数据结构中关于单链表的算法,将两个链表有序链合并成一个非递归有序的单链表,并不占用其他的存储空间

#include <iostream.h>
#include "three2.h"
istream & operator>>(istream & in,List<T>inList)
{
	T value;ListNode<T> * P,* q,* s;
	in >> value;
    while (value!=inList.first->data)
	{
		s=new ListNode<T>(value);
		q=first;p=inList.first->link;
		while (p!=null && p->data<=value){q=p;p=p->link;}
		q->link=s;s->link=p;
		if(p==null)inList.last=s;
		in>>value;
	}
}
ostream & operator<<(ostream & out,List<T> outList)
{
	cout<<"\nThe List is :\n";
	ListNode<T> * p=outList.first->link;
	while (p!=null)
	{
		out<<p->data;
		if (p!=last) out<<"->";
		else out<<endl;
		p=p->link;
	}
}
template<class T> void List<T> :: merge(List<T> & hb)
{
	ListNode<T> * pa,* pb,* q,* p;
	pa=first->link;pb=hb.first->link;
	first->link=null;
	while (pa!=null&&pb!=null)
	{
		if(pa->data<=pb->data){q=pa;pa=pa->link;}
		else {q=pb;pb=pb->link;}
		q->link=first->link;first->link=q;
	}
	p=(pa!=null) ? pa:pb;
	while (p!=null)
	{
		q=p;p=p->link;
		q->link=first->link;
		first->link=q;
	}
}