链表题目

结构体定义

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

题目：

//1.递归算法，删除不带头结点的单链表L中值为x的结点
void deletexinl(LinkLink &L,int x){
	if(L==NULL)return ;
	if(L->data == x){
		LinkList p = L;
		L = L->next;
		free(p);
		deletexinl(L,x);
	}else{
		deletexinl(L->next,x);
	}
}

//2.在带头节点的单链表L中，删除所有值为x的结点，释放空间（x不唯一)
int deletexinL(LinkList &L,int x){
	LinkList l,p,s;
	p = L;
	l = L->next;
	while(l){
		if(l->data == x){
			s = l;
			l = l->next;
			p->next = l;
			free(s);
		}else{
			p = l;
		    l = l->next;
		}	
	}
}  

//3.反向输出链表L的值
int printLreverse(LinkList L){
	if(!L)return 1;
	printLreverse(L->next);
	printf("%d",L->data);
} 

//4.删除带头结点的单链表最小值（唯一）的高效算法
void deleteminvalue(LinkList &L){
	LinkList l,p,s;
	p = L;
	s = p;
	l = L->next;
	int x = l->data;
	while(l){
		if(l->data < x){
			//保存被删除结点的前一个结点 
			s = p;
			x = l->data;
		}
		p = l;
		l = l->next;
	}
	p = s->next;
	s->next = p->next;
	free(p);
}

//5.就地逆转带头结点的链表(空间复杂度为o(1)) 
void reverseList(LinkList &L){
   LinkList p,c,r;
   p = NULL;
   c = L->next; 
  while(c){
  	r = c->next;
  	c->next = p;
  	p=c;
  	c=r;
  }
  L->next = p;
} 

//6.带头结点的链表排序（递增）
void InsertSort(LinkList &L){
	LinkList p,pre,r;
	p = L->next;
	r = p->next; //防止断链 
	p->next = NULL; //对第一个结点断链 
	p = r; //工作结点继续前进 
	while(p){
		r = p->next;
		pre = L;
		//在有序表内寻找合适的位置，找到大于当前结点结点的前一个结点指针 
		while(pre->next && pre->next->data < p->data ){
			pre = pre->next;
		}
		//移动操作 
		p->next = pre->next;
		pre->next = p;
		p = r;
	}
}

//7.(无序)删除带头单链表元素值在S-T之间的结点
void deletestotelem(LinkList &L,int s,int t){
    LinkList l,p,i;
	l = L->next;
	p = L;
	i = L;
	while(l){
		if(l->data>s && l->data<t){
			i = l;
			l = l->next;
			p->next = l;
			free(i);
		}else{
			p = l;
		    l = l->next;
		}
	} 
} 

//8.找出两个单链表的公共结点（假设带头） 
//思路：先找到两个链表的长度 做差等于k 长的那个链表先移动k个结点 之后同步移动两链表 找到公共结点即可！ 
LinkList findtwolistpnode(LinkList &m,LinkList &n){
	int mlength=0,nlength=0,k;
	LinkList l = m->next,s = n->next,max,min;
	//计算链表m的长度
	while(l){
		mlength++;
		l = l->next;
	}
	//计算链表n的长度
	while(n){
		nlength++;
		n = n->next;
	} 
	//比较链表长度大小
	if(mlength>nlength){
		k = mlength - nlength;
		max = m;
		min = n;
	}else{
		k = nlength - mlength;
		max = n;
		min = m;
	}
	//长链表移动k个结点 
	max = max->next;
	min = min->next;
	while(k>0){
		k--;
		max = max->next;
	} 
	//开始比较
	while(max && min){
		if(max == min){
			return max;
		}
		max = max->next;
		min = min->next;
	}
	return NULL;
}

//9.带表头的单链表L按递增次序输出结点并释放空间
//思路：每次输出最小的结点并依次删除 
void sortandfreel(LinkList &L){
	while(L->next){
	    LinkList p,pre,u;
	    pre = L;
	    p = pre->next;
	    //注意条件 
		while(p->next){
			//非常巧妙 直接利用next结点做比较 
			if(p->next->data < pre->next->data){
			  pre = p;
			}
			p = p->next;
		}
		printf("%d",pre->next->data); 
		u = pre->next;
		pre->next = u->next;
		free(u);
	}
	free(L);
}   

//10.单链表a分解为链表a与链表b，其中a包含链表的奇数结点，b包含链表的偶数结点，保持相对顺序不变
LinkList transintoaandb(LinkList &a){
	LinkList m,b,n,p,r;
	b = (LNode*)malloc(sizeof(LNode));
	b->next = NULL;
	b->data = -1;
	m = b;
	n = a->next;
	p = a;
	int i = 1;
	while(n){
		i++;
		if(i%2==0){
		   r = n;
		   n = n->next;
		   p->next = n;
		   r->next = NULL;
		   m->next = r; 
		   m = r;
		}else{
		   p = n;
		   n = n->next;
		} 
	}
	return b;
}

//11. 有带头单链表c={a1,b1,a2,b2,...}，将其分离为链表A={a1,a2...},链表B={b1,b2...}(要求算法就地)
LinkList divideintoAandB(LinkList &a){
	LinkList p,b,m,n,s;
	m = a->next;
	p = a;
	b = (LNode*)malloc(sizeof(LNode));
	b->next = NULL;
	b->data = -1; 
	n = b;
	int i=1;
	while(m){
		if(i%2==0){
			s = m; //保存偶数结点 
			m = m->next;
			p->next = m;
			s->next = n->next; //头插法 
			n->next = s;
		}else{
			p = m;
		    m = m->next;
		}
		i++;	
	}
	return b;
} 

//12.有序单链表去重（设有头结点） 
void removerepeat(LinkList &L){
	LinkList l,p,s;
	l = L->next;
	p = L;
	while(l){
		if(l->next && l->next->data == l->data){
			s = l;
			l = l->next;
			p->next = l;
			free(s);
		}else{
			p = l;
		    l = l->next;
		}
	} 
} 

//13.两个有序且递增单链表归并为一个递减的单链表，要求使用其中一个链表返回
void mergetwolist(LinkList &a,LinkList &b){
	LinkList m,n,s;
	m = a->next;
	n = b->next;
	a->next = NULL;
	//逆转插入链表A内,哪个小先插哪个 
	while(m && n){
		if(m->data <= n->data){
			s = m->next;
			m->next = a->next;
			a->next = m;
			m = s;
		}else{
			s = n->next;
			n->next = a->next;
			a->next = n;
			n = s;
		}
	}
	//有多余元素存链表B里 
	if(m){
		n = m;
	}
	//处理链表B剩下元素，插入链表A里 
	while(n){
		s = n->next;
		n->next = a->next;
	    a->next = n;
		n = s;
	}
	free(b);
} 

//14.带头结点递增有序的两个单链表AB，产生公共元素链表C，不破坏AB的结点
LinkList publicnode(LinkList A,LinkList B){
	LinkList c,a,b,r,s;
	c = (LNode*)malloc(sizeof(LNode));
	c->next = NULL;
	r = c;
	a = A->next;
	b = B->next;
	while(a && b){
		if(a->data > b->data){
			b = b->next;
		}else if(a->data < b->data){
			a = a->next;
		}else if(a->data == b->data){
			s = (LNode*)malloc(sizeof(LNode));
			s->next =NULL;
			s->data = a->data;
			r->next = s;
			r = s;
			a = a->next;
			b = b->next;
		}
	}
	return c;
}

//15.求递增序列的单链表A和B的交集，并放到单链表A内
void getAandBpublicnode(LinkList &A,LinkList &B){
	LinkList a,b,r;
	a = A->next;
	b = B->next;
	A->next = NULL;
	while(a && b){
		if(a->data < b->data){
			a = a->next;
		}else if(a->data > b->data){
			b = b->next;
		}else{
			r = a->next;
			a->next = A->next;
			A->next = a;
			a = r;
			b = b->next;
		}
	}
} 

//16.有单链表A与单链表B，判定B是不是A的连续子序列 
bool issubseq(LinkList A,LinkList B){
	LinkList a,b,s;
	int is = 0;
	a = A->next;
	b = B->next;
	while(a){
		if(a->data == b->data){
			s = a->next;
			while(b){
				if(a->data != b->data){
					//遇到不同的元素b归原位 
					b = B->next;
					//a恢复循环中的位置 
					a = s;
					is = 0;
					break;
				}
				b = b->next;
				a = a->next;
			}
			//b是否走完了？ 
			if(b == NULL){
				is = 1;
			}
			break;
		}
		a = a->next;
	}
	return is==1?true:false;
}

//17.判定带头的循环双链表是否对称
bool dlistissy(DLinkList L){
	DLinkList m,n;
	m = L->prior;
	n = L->next;
	while(m!=n && m->next != n){
		if(m->data !=n->data){
			return false;
			break;
		}
		m = m->prior;
		n = n->next;
	}
	return true; 
}

//18.循环单链表H1接到H2后面，链接完保持循环链表形式
//关键问题 找到尾部结点 
LinkList linktwolist(LinkList &A,LinkList &B){
	LinkList a,b;
	a = A;
	b = B
	while(a->next != A){
		a = a->next;
	} 
	while(b->next != B){
		b = b->next;
	}
	a->next = B;
	b->next = A;
	return A;
}

//19.有带头结点的循环单链表A，在该表中反复找到最小值点删除并输出，直到表空再删除表头
void deleteallnode(LinkList &L){
	while(L->next != L){
		LinkList p,l,s,p2;
		p = L;
		p2 = p;
		l = L->next;
		s = l;
		while(l!=L){
			if(l->data < s->data){
			  s = l;	
			  p2 = p;
			}
			p = l;
			l = l->next;
		}
		printf("%d ",s->data);
		p = s;
		p2->next = p->next;
		free(p);
		
	} 
	free(L);
}

//20.编写Locate(L,X)算法
void Locate(FDLinkList &L,int x){
	FDLinkList l,p,s;
	l = L->next;
	p = L;
	//寻找x结点 
	while(l){
		if(l->data == x)break; 
		p = l;
		l = l->next; 
	} 
	//找不到退出
	if(!x)return; 
	//除掉x结点
	s = l;
	l->next->prior = p; 
	p->next = l->next; 
	//频度加加 
	s->freq++;
	//找到适合的频度位置插入
	l = L->next;
	p = L;
	while(l){
		if(l->freq <= s->freq)break;
		p = l
		l = l->next;
	} 
	//插入
	if(l){
		//不在末尾，在表中间插入 
		s->next = l;
		s->prior = p;
		p->next = s;
		l->prior = s;
	}else{
		//在末尾插入
		s->next = NULL;
		s->prior = p;
		p->next = s; 
	}
} 

//21.判定链表是否有环
bool iscircleinlist(LinkList L){
	LinkList a,b;
	a = L->next;
	b = L->next;
	while(a && b){
		a = a->next;
		b = b->next->next;
		if(a == b)return true;
	}
	return false;
} 

//22（09统考).高效算法查找指定带头链表L的倒数第k个结点
LinkList findknode(LinkList L,int k){
	LinkList a,b;
	int i = 1; 
	a = b = L->next;
	while(a){
	  if(i>k){
	  	b = b->next;
	  }
	  a = a->next;
	  i++;
	}
	return b;
} 

//23.寻找两个单词的共同后缀
//取表长
int listlen(LinkList head){
	int len = 0;
	while(head->next){
		len++;
		head = head->next;
	}
	return len;
}  
//找共同后缀 
LinkList findpublic(LinkList a,LinkList b){
	int m,n;
	LinkList p,q;
	m = listlen(a);
	n = listlen(b);
	for(p=a;m>n;m--)p=p->next;
	for(q=b;n>m;n--)q=q->next;
	while(p->next && p->next!=q->next){
		p = p->next;
		q = q->next;
	}
	return p->next;
}

//24.删除链表中绝对值重复的结点
void deljnum(LinkList &a,int n){
	int x[n+1] = {0},y;
	LinkList l=a->next,p=a,s;
	while(l){
		//取绝对值 
		if(l->data < 0){
			y=-l->data;
		}else{
			y=l->data;
		}
		x[y]++;
		if(x[y]>1){
			s = l->next;
			p->next = s;
			free(l);
			l = s;
		}else{
		  p = l;
		  l = l->next;	
		}
		
	}
}