Old code: 《Data Structures》3-3, Operations on single list

datastruct_3-3.cpp

#include<iostream>
using namespace std;

struct Node {
  int key;
	Node *next;
};

Node * reverseList(Node *pHead){
/*
	一次遍历反转链表，并返回结果链表的头指针
*/
	if(pHead==NULL)return NULL;
	//依次从pHead上取下头结点插入到pSaveHead前面，同时更新pSaveHead
	Node *pSaveHead=pHead;
	pHead=pHead->next;
	pSaveHead->next=NULL;
	while( pHead!=NULL ){
		Node *pTmp=pHead;
		pHead=pHead->next;
		pTmp->next=pSaveHead;
		pSaveHead=pTmp;
	}
	return pSaveHead;
}

Node * mergeList(Node *ha, Node *hb){
/*
   ha,hb分别指向两个非递减的有序单链表
   mergeList合并ha,hb,返回一个非递增的链表的头指针
   要求：不占用其他存储空间（in space）
   例如：ha: 1-->1-->2-->4  hb:2-->3-->4
         合并后结果为：4-->4-->3-->2-->2-->1-->1
*/
	Node *pSaveHead=NULL;
	//pSaveHead指向结果链表的头结点
	if(ha==NULL && hb==NULL) return NULL;
	//Here: ha!=NULL 或者 hb!=NULL
	if(ha==NULL){
		pSaveHead=reverseList(hb);
		return pSaveHead;
	}
	if(hb==NULL){
		pSaveHead=reverseList(ha);
		return pSaveHead;
	}
	//Main Code Starts Here:
	pSaveHead=(ha->key < hb->key )? ha : hb;
	if(pSaveHead==ha)
		ha=ha->next;
	else
		hb=hb->next;
	//设置结果链表的最后一个next域为空
	pSaveHead->next=NULL;
	//循环开始：
	while(ha!=NULL && hb!=NULL){
		//取ha,hb两个结点中小的那一个，然后插到pSaveHead的前面
		Node *pSmall=(ha->key < hb->key)?ha:hb;
		//修改ha或hb使得它们正确地指向下一个Node:
		if(pSmall==ha)
			ha=ha->next;
		else
			hb=hb->next;
		//把pSmall结点插入到pSaveHead的前面：
		pSmall->next=pSaveHead;
		//同时更新pSaveHead:
		pSaveHead=pSmall;
	}
	//处理ha,hb中有一个不为NULL的情况:
	Node *pLeft=(ha==NULL)?hb:ha;
	//依次从pLeft指向的链表取下头结点，再插入到pSaveHead的前面
	//这实际上就是一次遍历反转链表的思路
	while( pLeft!=NULL ){
		Node *pTmp=pLeft;
		pLeft=pLeft->next;
		pTmp->next=pSaveHead;
		pSaveHead=pTmp;
	}
	return pSaveHead;
}

//----------------TEST TEST-----------------------/
//为方便测试，这里给出一个从数组创建链表的函数
Node * makeList(int A[], int length){
	//两种方法：从前面插入或者从尾部添加，这里用第一种方法
	Node *pHead=NULL;
	for(int j=length-1;j>=0;j--){
		Node *p=new Node();
		p->key=A[j];
		p->next=pHead;
		pHead=p;
	}
	return pHead;
}

void removeList(Node *pHead){
	while(pHead!=NULL){
		Node *p=pHead;
		pHead=pHead->next;
		delete p;
	}
}

void viewList(Node *p){
	if(p==NULL){
		cout<<"NULL List."<<endl;
		return;
	}
	cout<<p->key;
	p=p->next;
	while(p!=NULL){
		cout<<"-->"<<p->key;
		p=p->next;
	}
	cout<<endl;
}
int main(){
	int A[]={1,1,2,4};
	int B[]={2,3,4};
	Node *ha=makeList(A,4);
	viewList(ha);
	Node *hb=makeList(B,3);
	viewList(hb);
	Node *p=mergeList(ha,hb);
	viewList(p);
	return 0;
}