链表求交和并

链表是面试中常见的题目之一。下面列出常见的链表面试题。

本随笔主要针对两链表求并，求交。

1）【链表反向按序求并】两个按递增次序排列的单链表，编写算法合并，按递减次序排列，并要求利用原来两个单链表的结点存放新的链表。 

LinkList Union(LinkList la,lb) 
{ 
	pa=la->next; 
	pb=lb->next;// pa,pb是工作指针
	la->next=null;// la为结果链表的头指针
	while(la&&lb) 
	{ 
		if(pa->data<=pb->data) 
		{ 
			r=pa->next;// 将pa的后继暂存于r
			pa->next=la->next;// 将pa的结果存于结果表中，同时逆置
			la->next=pa; 
			pa=r;// 恢复pa为当前待比较结点
		} 
		else
		{ 
			r=pb->next;// 将pa的后继暂存于r
			pb->next=la->next;// 将pb的结果存于结果表中，同时逆置
			la->next=pb; 
			pb=r;// 恢复pb为当前待比较结点
		} 
		if(pa) pb=pa;// 避免对pa再写如下的while语句
		while(pb!=null) 
		{ 
			r=pb->next; 
			pb->next=la->next; 
			la->next=pb; 
			pb=r; 
		} 
	} 
} 

 2)两链表递增有序，合并后依然有序，但是要求不带重复元素 

#include "stdafx.h"
#include<iostream>
using namespace std;
typedef struct node
{
	int data;
	struct node *next;
}Listnode,*LinkList;
int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}
void Merge(LinkList &La,LinkList &Lb,LinkList &Lc)
{
	LinkList pa,pb,pc,u;
	pa=La->next,pb=Lb->next;
	Lc=pc=La;
	while(pa&&pb)
	{
		if(pa->data<pb->data)
		{
			pc->next=pa;
			pc=pa;
			pa=pa->next;
		}
		else if(pa->data>pb->data)
		{
			pc->next=pb;
			pc=pb;
			pb=pb->next;
		}
		else     //关键步，处理相等的元素
		{
			pc->next=pb;
			pc=pb;
			pb=pb->next;
			u=pa;
			pa=pa->next;
			free(u);
		}
		if(pa)pc->next=pa;else pc->next=pb;
		free(Lb);
	}
}

 3)两个带头结点的链表从小到大排序，求两个链表的交集，要求依旧从小到大排序，没有重复元素。

#include "stdafx.h"
#include<iostream>
using namespace std;
typedef struct node
{
	int data;
	struct node *next;
}Listnode,*LinkList;
int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}
void Merge(LinkList &La,LinkList &Lb,LinkList &Lc)
{
	LinkList pa,pb,pc,u;
	pa=La->next,pb=Lb->next;
	Lc=pc=La;
	while(pa&&pb)
	{
		if(pa->data<pb->data)
		{
			u=pa;
			pa=pa->next;
			free(u);
		}
		else if(pa->data>pb->data)
		{			
			pb=pb->next;
		}
		else
		{
			if(pc==La)   //处理第一个相等的元素
			{
				pc->next=pa;pc=pa;pa=pa->next;
			}
			else if(pc->data==pa->data)   //重复元素不进入La表
			{
				u=pa;
				pa=pa->next;free(u);
			}
			else    //交集元素并入结果表
			{
				pc->next=pa;pc=pa;pa=pa->next;
			}
		}
		while(pa)  //删除La表剩余元素
		{
			u=pa;pa=pa->next;free(u);
		}
		free(Lb);
	}
}