速通数据结构链表代码题

头文件

#include <iostream>
using namespace std;
typedef struct LNode
{
	int data;
	struct LNode *next;
} LNode, *Linklist;


//不带头节点的链表
Linklist aaaa();
//带头节点的链表
Linklist bbbb();

#include <iostream>
using namespace std;
//循环单链表
typedef struct LNode
{
	int data;
	struct LNode *next;
} LNode, *Linklist;

Linklist dddd();

#pragma once
#include <iostream>
using namespace std;
//循环双链表
typedef struct DNode
{
	int data;
	struct DNode *next, *prior;
} DNode, *Dinklist;

Dinklist cccc();

#include"linklist.h"
//不带头节点的链表
Linklist aaaa()
{
	LNode *L = new LNode;
	int a;
	cin >> a;
	L->data = a;
	LNode *p = L; //声明一个指针指向头结点，
	//生成链表
	cin >> a;
	while (a != 0)//输入0为循环的结束条件
	{
		LNode *q = new LNode;
		q->data = a;
		q->next = NULL;
		p->next = q;
		p = p->next;
		cin >> a;
	}
	p->next = NULL;
	return L;
}

//带头节点的链表
Linklist bbbb()
{
	LNode *L = new LNode; //创建一个头结点
	LNode *p = L;         //声明一个指针指向头结点
	//生成链表
	int a;
	cin >> a;
	while (a != 0)
	{
		LNode *q = new LNode;
		q->data = a;
		q->next = NULL;
		p->next = q;
		p = p->next;
		cin >> a;
	}
	p->next = NULL;
	return L;
}

#include"circlesinglefun.h"
Linklist dddd()
{
	LNode *L = new LNode;
	LNode *p = L;
	int a;
	cin >> a;
	while (a != 0)
	{
		LNode *q = new LNode;
		q->data = a;
		q->next = NULL;
		p->next = q;
		p = p->next;
		cin >> a;
	}
	p->next = L;
	return L;
}

#include"circledoublefun.h"
Dinklist cccc() {
	DNode *L = new DNode;
	DNode *p = L;
	int a;
	cin >> a;
	while (a != 0)
	{
		DNode *q = new DNode;
		q->data = a;
		q->next = NULL;
		q->prior = p;
		p->next = q;
		p = p->next;
		cin >> a;
	}
	p->next = L;
	L->prior = p;
	return L;
}

设计一个递归算法，删除不带头节点的单链表L中所有值为x的结点

#include <iostream>
using namespace std;
#include"linklist.h"
/*
	设计一个递归算法，删除不带头节点的单链表L中所有值为x的结点

	5 2 4 6 2 0   0为for循环结束的标志
	5 4 6
*/

void del_x(LNode *&L, int x)//删除操作 参数是链表和要删除的结点的值
{
	LNode *p;
	if (L == NULL)	return;
	if (L->data == x)
	{
		p = L;//记录位置
		L = L->next;//后移操作 进行第二轮递归的操作时候 L->next=L->next->next 
		free(p);
		del_x(L, x);
	}
	else
		del_x(L->next, x);//递归函数 这里是不会断链的 (将L->next带入上述的操作时候)
}

int main01()
{
	LNode *L = aaaa();
	del_x(L, 2);
	while (L != NULL)
	{
		cout << L->data << " ";
		L = L->next;
	}
	return EXIT_SUCCESS;
}
/*
为什么这段代码不会导致链表断链呢？因为在递归过程中，只有当满足条件（L->data == x）时，才进行删除操作，并在删除操作之后再次递归调用del_x(L, x)，这样保证了删除节点后，将正确的下一个节点连接到当前节点，不会造成链表断链。而对于不满足条件的节点，直接通过递归调用del_x(L->next, x)进行下一个节点的处理，也不会引起链表断链
*/

删除带头节点单链表中所有值为x的结点

#include <iostream>
using namespace std;
#include"linklist.h"
/*
	删除带头节点单链表中所有值为x的结点

	删除结点的话 要知道链表的前一个结点才能删除
	
	  p
	头节点-->3-->4-->7-->4

	  p      q	  
	头节点-->3-->4-->7-->4

*/

//方法1
void del(LNode *&L, int x)
{
	LNode *p = L->next, *pre = L;//初始化 
	LNode *q;
	while (p != NULL)
	{
		if (p->data == x)
		{
			q = p;//用q来保存要删除元素的地址 进行删除操作 p是要用来后面进行遍历
			pre->next = p->next;
			p = p->next;//继续往后遍历
			free(q);
		}
		else
		{
			pre = p;
			p = p->next;
		}
	}
}

//方法2
void Del(LNode *&L, int x)
{
	LNode *p = L;
	while (p->next != NULL)
	{
		if (p->next->data == x)
		{
			LNode *q = p->next;
			p->next = q->next;
			free(q);
		}
		else
			p = p->next;
	}
}

int main02()
{
	LNode *L = bbbb();
	Del(L, 4);
	LNode *q = L->next;
	while (q != NULL)
	{
		cout << q->data << " ";
		q = q->next;
	}
	return EXIT_SUCCESS;
}

删除带头结点单链表中第一个值为x的结点

#include <iostream>
#include "linklist.h"
using namespace std;
/*
	删除带头结点单链表中第一个值为x的结点

	3 4 2 3 2 2 2 
	3 4 3 2 2 2 
*/

//方法1
int finddelete(LNode *&C, int x)
{
	LNode *p, *q;
	p = C;
	while (p->next != NULL)
	{
		if (p->next->data == x)
			break;
		//break语句执行后 此时的p保留到下一次的操作、
		//执行break语句后，栈区的数据不会被立即释放。在程序执行到break语句时，会跳出当前循环并继续执行循环之后的代码，但是栈上的数据仍然存在，并且可以在后续代码中继续访问
		else
			p = p->next;
	}

	if (p->next == NULL)//到底了
		return 0;
	else
	{
		q = p->next;
		p->next = q->next;
		free(q);
		return 1;
	}
}

//方法2
void finddelete2(LNode *&C, int x)
{
	LNode *p, *q;
	p = C;
	while (p->next != NULL) 
	{
		if (p->next->data == x)
		{
			q = p->next;
			p->next = q->next;
			free(q);
			return;
		}
		else
			p = p->next;
	}
	return;
}

int main03()
{
	LNode *L = bbbb();
	//finddelete(L, 2);
	finddelete2(L, 2);
	LNode *q = L->next;
	while (q != NULL)
	{
		cout << q->data << " ";
		q = q->next;
	}
	return 0;
}

从尾到头反向输出每个单链表的值

#include <iostream>
#include "linklist.h"
using namespace std;
/*
	从尾到头反向输出每个单链表的值

	递归
	思想:将除了第一个结点的结点反向输出，然后再输出第一个结点
	                                                                                                      弱智
	3 8 7 2
	2 7 8 3
*/

void print(LNode *L)
{
	if (L->next != NULL)
	{
		print(L->next);
	}
	cout << L->data << " ";
}

int main04()
{
	LNode *L = bbbb();
	print(L->next);//递归操作

	return EXIT_SUCCESS;
}

编写一个算法让单链表就地逆置

#include <iostream>
#include "linklist.h"
using namespace std;
  
/*
	编写一个算法让单链表就地逆置

	1、头插法
	2、三指针法 让链表的结点依次变为 第一个结点的next指向null 5-->3 2-->5 10-->2 最后头节点指向10

	L-->3-->5-->2-->10

	L-->10-->2-->5-->3
*/

//方法1 头插法
void reverse(LNode *&L)
{
	LNode *p = L->next, *r;//r是用来记录p之后的下一个结点
	L->next = NULL;//头节点的next指针指向null 用于进行头插
	while (p != NULL)
	{
		r = p->next;
		p->next = L->next;
		L->next = p;
		p = r;//头插法 执行完了之后p的next指针指向的是null，因此需要r指针来记录原来的链表的p的next指针域指向的结点
	}
}

//方法2 三指针
void Reverse(LNode *&L)
{
	LNode *p = L->next, *r = p->next;
	LNode *pre;//初始值是p的位置 是用来记录p的前一个结点 用于怕p->next=pre
	p->next = NULL;//将第一个结点的next指针域指向置为null 作为出口
	while (r != NULL)
	{
		pre = p;
		p = r;
		r = r->next;
		p->next = pre;
	}
	L->next = p;
}

int main05()
{
	LNode *L = bbbb();
	reverse(L);
	LNode *q = L->next;
	while (q != NULL)
	{
		cout << q->data << " ";
		q = q->next;
	}
	return 0;
}

从链表中删除给定值在s到t之间的所有元素(不包括s和t)

#include <iostream>
#include "linklist.h"
using namespace std;
/*
	从链表中删除给定值在s到t之间的所有元素(不包括s和t)
	3 6 19 8 7 10 5

	3 19 10 5

*/

void del(LNode *&L, int min, int max)
{
	LNode *p = L;
	while (p->next != NULL)
	{
		if (p->next->data > min && p->next->data < max)
		{
			LNode *u = p->next;//指针u 便于删除
			p->next = u->next;
			free(u);
		}
		else
			p = p->next;
	}
}

int main06()
{
	LNode *L = bbbb();
	del(L, 5, 10);
	LNode *q = L->next;
	while (q != NULL)
	{
		cout << q->data << " ";
		q = q->next;
	}
	return EXIT_SUCCESS;
}

删除带头节点的单链表中最小值

/*

	删除带头节点的单链表中最小值

	L-->4 10 2 12 7

	L-->4 10 12 7

*/

#include <iostream>
#include "linklist.h"
using namespace std;

void del_min2(LNode *&L)
{
	LNode *p = L;
	LNode *minp = L;
	while (p->next != NULL)
	{
		//第一次是不满足这个条件的  p往后移动
		if (p->next->data < minp->next->data)
			minp = p;
		p = p->next;
	}
	LNode *u = minp->next;
	minp->next = u->next;
	free(u);
}

int main07()
{ 
	LNode *L = bbbb();
	del_min2(L);
	LNode *q = L->next;
	while (q != NULL)
	{
		cout << q->data << " ";
		q = q->next;
	}
	return 0;
}

删除不带头节点的单链表中最小的元素

#include <iostream>
#include"linklist.h"
using namespace std;
/*
	删除不带头节点的单链表中最小的元素
*/
void del_min(LNode *&L)
{
	LNode *minp = L;
	LNode *p = L->next;
	while (p != NULL)
	{
		if (p->data < minp->data)
			minp = p;
		p = p->next;
	}
	if (L == minp)
	{
		L = L->next;
		free(minp);
		return;
	}
	p = L;
	while (p->next != minp)
		p = p->next;
	p->next = minp->next;
	free(minp);

}

int main08()
{
	LNode *L = aaaa();
	del_min(L);
	LNode *q = L;
	while (q != NULL)
	{
		cout << q->data << " ";
		q = q->next;
	}
	return 0;
}

给定一个单链表，按递增排序输出的单链表中各结点的数据元素，并释放节点所占空间

#include <iostream>
#include "linklist.h"
using namespace std;
/*
	给定一个单链表，按递增排序输出的单链表中各结点的数据元素，并释放节点所占空间

	1、依次找到这个单链表最小的元素 
	2、依次进行释放操作

	3 4 2 1 5
	1 2 3 4 5
*/
void del_min10086(LNode *&head)
{
	while (head->next != NULL)//循环条件 head后面为null时 循环结束
	{
		LNode *pre = head;
		LNode *p = head->next;
		while (p->next != NULL)
		{
			if (p->next->data < pre->next->data)
			{
				pre = p;
			}
			p = p->next;
		}
		cout << pre->next->data << " ";
		LNode *u = pre->next;//u记录最小的元素
		pre->next = u->next;
		free(u);
	}
	free(head);
}

int main09()
{
	LNode *L = bbbb();
	del_min10086(L);
	return EXIT_SUCCESS;
}

将一个带头节点的单链表A分解成两个带头节点的单链表A和B使A中含奇数位置元素，B中含偶数位置元素，且相对位置不变

/*
	堆区申请一个数组
	c语言 int *A=(int *)malloc(sizeof(int)*n)
	c++   int *A=new int[n]
*/


#include<iostream>
using namespace std;
#include"linklist.h"
/*
	奇偶链表 这里的奇偶是数组下标的奇偶

	将一个带头节点的单链表A分解成两个带头节点的单链表A和B
	使A中含奇数位置元素，B中含偶数位置元素，且相对位置不变

	L-->4-->10-->7-->6-->15

	A-->4-->7-->15

	B-->10-->6
*/

Linklist create1(LNode *&A)
{
	LNode *B = new LNode;//堆区申请一个结点
	//c语言写法 LNode *B = (LNode*)malloc(sizeof(LNode));
	B->next = NULL;//将新建立的结点的next域置空
	LNode *ra = A, *rb = B, *p = A->next;//p记录A的头节点的下一个结点
	A->next = NULL;
	while (p != NULL)
	{
		ra->next = p;
		ra = p;
		p = p->next;
		rb->next = p;
		rb = p;
		//p = p->next; err 奇数链表的时候 p最后指向的是null null是没有next域的
		//偶数链表的时候不需要这样写if
		if (p != NULL)
			p = p->next;
	}
	ra->next = NULL;//奇数链表的时候ra->next=null本来就是存在的 偶数链表的时候要进行说明
	return B;
}

int main10()
{
	LNode *A = bbbb();
	LNode *B = create1(A);
	LNode *q = A->next;
	LNode *p = B->next;
	cout << "A: ";
	while (q != NULL)
	{
		cout << q->data << " ";
		q = q->next;
	}
	cout << endl;
	cout << "B: ";
	while (p != NULL)
	{
		cout << p->data << " ";
		p = p->next;
	}
	return EXIT_SUCCESS;
}

将一个单链表{a1,b1,a2,b2……an,bn}拆分成{a1,a2,……,an}和{bn,bn-1,……,b1}

#include <iostream>
#include "linklist.h"
using namespace std;
/*
	将一个单链表{a1,b1,a2,b2……an,bn}拆分成{a1,a2,……,an}和{bn,bn-1,……,b1}
	由题意得这个单链表是偶数个
	拆分的第一个是奇链表，拆分的第二个是逆序的偶链表（用头插法来进行表示)
*/

Linklist create(LNode *&A)
{
	LNode *B = new LNode;
	B->next = NULL;
	LNode *ra = A, *p = A->next, *q;
	A->next = NULL;
	while (p != NULL)
	{
		ra->next = p;
		ra = p;
		p = p->next;
		q = p;
		if (q == NULL)//如果是奇数链表的时候加上这句话 偶数则不用加入 指向null的时候就不需要进行头插了
			break;//??
		p = p->next;
		q->next = B->next;
		B->next = q;
	}
	ra->next = NULL;//把A链表断开
	return B;
}

int main11()
{
	LNode *A = bbbb();
	LNode *B = create(A);
	LNode *q = A->next;
	LNode *p = B->next;
	cout << "A ";
	while (q != NULL)
	{
		cout << q->data << " ";
		q = q->next;
	}
	cout << "B ";
	while (p != NULL)
	{
		cout << p->data << " ";
		p = p->next;
	}
	return 0;
}

删除递增链表中重复的元素 并且保留这些重复的元素的其中一个

#include <iostream>
#include "linklist.h"
using namespace std;
/*
	删除递增链表中重复的元素  并且保留这些重复的元素的其中一个
	3 4 4 4 5 5
	3 4 5
*/
void del111(LNode *&L)
{
	LNode *p = L->next;//指向第一个有元素的位置
	//LNode *q;
	if (p == NULL)
		return;
	while (p->next != NULL)
	{
		LNode* q = p->next;//指向第二个有元素的位置 保持在p的后一个位置就好了
		if (p->data == q->data)
		{
			p->next = q->next;
			free(q);
		}
		else
			p = p->next;
	}
}

int main12()
{
	LNode *A = bbbb();
	del111(A);
	LNode *q = A->next;
	cout << "A ";
	while (q != NULL)
	{
		cout << q->data << " ";
		q = q->next;
	}
	return EXIT_SUCCESS;
}

两个递增有序的单链表, 设计算法成一个非递减有序的链表

#include <iostream>
#include "linklist.h"
using namespace std;

/*
	两个递增有序的单链表, 设计算法成一个非递减有序的链表

	A-->2-->5-->9-->13
	B-->4-->7
*/

void fun10(LNode *&A, LNode *&B)
{
	LNode *p = A->next, *q = B->next;
	LNode *ra = A;//假设A为合并之后的链表
	A->next = NULL;
	B->next = NULL;
	while (p != NULL && q != NULL)
	{
		if (p->data <= q->data)
		{
			ra->next = p;
			//ra = p;
			//p = p->next;
			p = p->next;
			ra = ra->next;
		}
		else
		{
			ra->next = q;
			q = q->next;
			ra = ra->next;
		}
	}
	//两个链表之间的长度可能会不相等
	if (p != NULL)
		ra->next = p;
	if (q != NULL)
		ra->next = q;
}

int main13()
{
	cout << "A:";
	LNode *A = bbbb();
	cout << "B:";
	LNode *B = bbbb();
	fun10(A, B);
	LNode *q = A->next;
	cout << "A+B:";
	while (q != NULL)
	{
		cout << q->data << " ";
		q = q->next;
	}
	return EXIT_SUCCESS;
}

两个递增有序的单链表 设计算法成一个非递增有序的链表

#include <iostream>
#include "linklist.h"
using namespace std;

/*
	两个递增有序的单链表 设计算法成一个非递增有序的链表

	头插法

	A--2--5--9--13
	B--4--7
*/

void fun23(LNode *&A, LNode *&B)
{
	LNode *p = A->next, *q = B->next, *s;
	A->next = NULL;
	B->next = NULL;
	while (p != NULL && q != NULL)
	{
		if (p->data <= q->data)
		{
			s = p;
			p = p->next;
			s->next = A->next;
			A->next = s;
		}
		else
		{
			s = q;
			q = q->next;
			s->next = A->next;
			A->next = s;
		}
	}
	while (p != NULL)
	{
		s = p;
		p = p->next;
		s->next = A->next;
		A->next = s;
	}
	while (q != NULL)
	{
		s = q;
		q = q->next;
		s->next = A->next;
		A->next = s;
	}
}

int main14()
{
	cout << "A:";
	LNode *A = bbbb();
	cout << "B:";
	LNode *B = bbbb();
	fun23(A, B);
	LNode *q = A->next;
	cout << "A:";
	while (q != NULL)
	{
		cout << q->data << " ";
		q = q->next;
	}
	return 0;
}

A, B两个单链表递增有序，从A,B中找出公共元素产生单链表C，要求不破环A,B结点

#include <iostream>
#include "linklist.h"
using namespace std;

/*
	A, B两个单链表递增有序，从A,B中找出公共元素产生单链表C，要求不破环A,B结点

	1 3 4 5
	3 4 5

	这题是要新建结点的 不需要free原来的结点
	3 4 5
*/

Linklist common(LNode *A, LNode *B)
{
	LNode *p = A->next;
	LNode *q = B->next;
	LNode *C = new LNode;//创一个头节点
	LNode *r = C;// , *s;
	while (p != NULL && q != NULL)
	{
		if (p->data < q->data)//p小p右移
			p = p->next;
		else if (p->data > q->data)//q小q右移
			q = q->next;
		else//相等的情况
		{
			LNode* s = new LNode;
			s->data = p->data;
			r->next = s;
			r = s;
			p = p->next;//继续往后找
			q = q->next;
		}
	}
	r->next = NULL;
	return C;//要返回头节点 因此需要定义r指针来指针C进行操作
}

int main15()
{
	cout << "A:";
	LNode *A = bbbb();
	cout << "B:";
	LNode *B = bbbb();
	LNode *C = common(A, B);
	LNode *q = C->next;
	while (q != NULL)
	{
		cout << q->data << " ";
		q = q->next;
	}
	return 0;
}

A, B两个单链表递增有序，从A，B中找出公共元素并存放于A

#include <iostream>
#include "linklist.h"
/*
	A, B两个单链表递增有序，从A，B中找出公共元素并存放于A
	
	A 4 6 7 10 19
	B 3 4 7 9
	
	A 4 7
	
*/
using namespace std;

void Union(LNode *&A, LNode *&B)
{
	LNode *p = A->next;
	LNode *q = B->next;
	LNode *ra = A, *u;//ra时刻处于最后一个结点的位置
	while (p != NULL && q != NULL)
	{
		if (p->data < q->data)
		{
			u = p;
			p = p->next;
			free(u);
		}
		else if (p->data > q->data)
		{
			u = q;
			q = q->next;
			free(u);
		}
		else
		{
			ra->next = p;//连接
			ra = p;
			p = p->next;//后移进行比较
			u = q;
			q = q->next;
			free(u);
		}
	}
	while (p != NULL)
	{
		u = p;
		p = p->next;
		free(u);
	}
	while (q != NULL)
	{
		u = q;
		q = q->next;
		free(u);
	}
	ra->next = NULL;
	free(q);
}

int main16()
{
	cout << "A:";
	LNode *A = bbbb();
	cout << "B:";
	LNode *B = bbbb();
	Union(A, B);
	LNode *q = A->next;
	while (q != NULL)
	{
		cout << q->data << " ";
		q = q->next;
	}
	return 0;
}

两个序列分别为A、B，将其存放到链表中, 判断B是否是A的连续子序列

#include <iostream>
#include "linklist.h"
using namespace std;

/*
	两个序列分别为A、B，将其存放到链表中, 判断B是否是A的连续子序列
	
	A 3 7 9 12
	B 7 9 12
	B是A的连续子序列 序列为7 9 12

	A 4 15 10 4 15
	B 4 15 1
	无子序列
*/

int seq(LNode *A, LNode *B)
{
	LNode *p = A->next;
	LNode *pre = p;//是用来进行匹配失败操作时所定义的指针 因为匹配失败更新p的位置 
	LNode *q = B->next;//初始匹配的位置
	while (p != NULL && q != NULL)
	{
		if (p->data == q->data)
		{
			p = p->next;
			q = q->next;
		}
		else
		{
			//方法二
			//p = p->next;

			pre = pre->next;//匹配失败后从下一个结点开始
			p = pre;//p移动到pre的位置
			q = B->next;//q从头开始匹配
		}
	}
	if (q == NULL)//匹配成功
		return 1;
	else
		return 0;
}

int main17()
{
	cout << "A:";
	LNode *A = bbbb();
	cout << "B:";
	LNode *B = bbbb();
	cout << "A:" << seq(A, B);
	return 0;
}

查找单链表中倒数第k个结点，若成功，则输出该节点的data，并返回1，否则返回0

#include <iostream>
#include "linklist.h"
using namespace std;
/*
	查找单链表中倒数第k个结点，若成功，则输出该节点的data，并返回1，否则返回0
	1、双指针
	2、暴力解法

	4 10 6 8

*/

//法一标准解
int find(LNode *head, int k)
{
	LNode *q = head->next;
	LNode *p = head;
	int i = 1;//i用来记录p和q之间的距离 初始值为1
	while (q->next != NULL)
	{
		q = q->next;
		++i;
		//if (i >= k)//为了保证p和q之间的距离为k 距离为k时候 在同时后移的情况就能解决此题
		//	p = p->next;
	}
	while (i >= k) {//为了保证p和q之间的距离为k 距离为k时候 在同时后移的情况就能解决此题
		p = p->next;
		--i;
	}
	//while (q != head->next)
	//{
	//	p = p->next;
	//	q = q->next->next;
	//	++i;
	//}
	if (p == head)
		return 0;
	else
	{
		cout << "倒数第3个节点为：" << p->data << endl;
		return 1;
	}
}

//法二暴力解
//倒数第k个结点就是正数第n-k+1个结点
int len(LNode *L)
{
	LNode *p = L->next;
	int n = 0;
	while (p != NULL)
	{
		p = p->next;
		++n;
	}

	cout << "n=" << n << endl;
	//return n;//返回的是结点的个数
}

int Find(LNode *L, int k)
{
	int i = 0, m;
	m = len(L) - k + 1;
	if (m <= 0)
	{
		return 0;
	}
	while (i < m)//正数第几个 如果0<2 就往后移动两次 就是正数第二个
	{
		L = L->next;
		++i;
	}
	cout << L->data;
	return 1;
}

int main()
{
	LNode *L = bbbb();
	int j = find(L, 3);
	//len(L);
	cout << "j=" << j << endl;
	return 0;
}

用单链表保存m个整数，并且|data|≤n, 要求设计时间复杂度尽可能高效的算法 对于data绝对值相等的点，仅保留第―次出现的点

/*
	用单链表保存m个整数，并且|data|≤n, 要求设计时间复杂度尽可能高效的算法
	对于data绝对值相等的点，仅保留第―次出现的点
	


	4 -3 -4 2 -3

	空间换时间
	4 -3 2
*/
#include <iostream>
#include "linklist.h"
using namespace std;

void fun(LNode *&head, int n)
{
	LNode *p = head;
	LNode *r;
	int *q = new int[n + 1];
	int m;//存储数据
	for (int i = 0; i < n + 1; ++i)
		q[i] = 0;
	while (p->next != NULL)
	{
		if (p->next->data > 0)
			m = p->next->data;
		else
			m = -p->next->data;
		//在数组中记数 如果绝对值相等的数出现了记为1 如果又出现了则删除后面一个
		if (q[m] == 0)
		{
			q[m] = 1;
			p = p->next;
		}
		else
		{
			//删除操作
			r = p->next;
			p->next = r->next;
			free(r);
		}
	}
	free(q);
}

int main19()
{
	LNode *L = bbbb();
	fun(L, 50);
	L = L->next;
	while (L != NULL)
	{
		cout << L->data << " ";
		L = L->next;
	}
	return EXIT_SUCCESS;
}

判断带头结点的循环双链表是否对称

#include <iostream>
#include "circledoublefun.h"
using namespace std;
/*
	判断带头结点的循环双链表是否对称

	循环双链表：

	   -------------------------------------------------
	prev head next ---- prev data next ----  prev data next
	   -------------------------------------------------
*/
int fun(DNode *L)
{
	DNode *p = L->next;
	DNode *q = L->prior;
	while (p != q && q->next != p)//分奇数和偶数进行判断 条件
		if (p->data == q->data)//判断对称的条件
		{
			//p往后移动 q往前移动
			p = p->next;
			q = q->prior;
		}
		else
			return 0;
	return 1;
}

int main20()
{
	DNode *A = cccc();

	cout << fun(A) << endl;
	return 0;
}

有两个循环单链表，链表头指针分别为h1,h2,试编写函数将h2链表接到h1之后,要求链接后仍保持循环链表形式

#include <iostream>
#include "circlesinglefun.h"
using namespace std;

/*
	有两个循环单链表，链表头指针分别为h1,h2,试编写函数将h2链表接到h1之后,要求链接后仍保持循环链表形式

	head next---data next----data next 
	 -------------------------------
*/

void link(LNode *&h1, LNode *&h2)
{
	LNode *p, *q;
	p = h1, q = h2;
	//p q走到循环单链表最后一个结点
	while (p->next != h1)
		p = p->next;
	while (q->next != h2)
		q = q->next;
	p->next = h2;//连接
	q->next = h1;//循环
}

int main21()
{
	LNode *A = dddd();
	LNode *B = dddd();
	link(A, B);
	LNode *q = A->next;
	while (q != A)
	{
		cout << q->data << " ";
		q = q->next;
	}
	return 0;
}

设有一个带头结点的循环单链表，其结点值为正整数设计算法反复找出链表内最小值并不断输出,并将结点从链表中删除,直到链表为空，再删除表头结点

#include <iostream>
#include "circlesinglefun.h"
using namespace std;
/*
	设有一个带头结点的循环单链表，其结点值为正整数
	设计算法反复找出链表内最小值并不断输出,并将结点从链表中删除,直到链表为空，再删除表头结点

	L--2--4--7--1--3
	L--2--4--7--3               输出1
*/


void del(LNode *&L)
{
	LNode *p, *minp, *u;
	while (L->next != L)
	{
		p = L->next;
		minp = L;
		while (p->next != L)//循环结束的条件
		{
			if (p->next->data < minp->next->data)
				minp = p;
			p = p->next;
		}
		cout << "依次输出为：";
		cout << minp->next->data << endl;
		u = minp->next;
		minp->next = u->next;
		free(u);
	}
	free(L);
}

int main22()
{
	cout << "输入A链表：";
	LNode *A = dddd();
	del(A);
	return 0;
}

判断单链表是否有环

#include <iostream>
#include "linklist.h" 
using namespace std;

/*
	判断单链表是否有环 

	用快慢指针法
	快指针走两步 慢指针走一步 相遇就证明是有环的

*/
int findloop(LNode *L)
{
	LNode *fast = L, *slow = L;
	while (fast != NULL && fast->next != NULL)
	{
		slow = slow->next;
		fast = fast->next->next;
		if (slow == fast)
			return 1;
	}
	return 0;
}

int main23()
{
	LNode *L = bbbb();
	cout << "A:" << findloop(L);
	return 0;
}

给定一个单链表L(a1,a2,a3,……,an)将其重新排列为(a1,an,a2,an-1,……)

#include <iostream>
#include "linklist.h"
using namespace std;
/*
	给定一个单链表L(a1,a2,a3,……,an)将其重新排列为(a1,an,a2,an-1,……)
	
	1 2 3 4 5
	1 5 2 4 3

	1 2 3 4 5 6
	1 6 2 5 3 4
*/

//中点之后的结点的操作
Linklist divrev(LNode *&L)
{
	//快慢指针找到链表的中点
	LNode *p = L, *q = L;
	while (q != NULL && q->next != NULL)//奇链表和偶链表结束的条件
	{
		p = p->next;
		q = q->next->next;
	}
	LNode *L1 = new LNode;
	L1->next = p->next;//新的结点连接到中点的后面的结点
	p->next = NULL;//将中点后的next指向NULL
	//中点之后的链表结点进行逆置操作 用头插法
	LNode *p1 = L1->next, *r;
	L1->next = NULL;
	while (p1 != NULL)//逆置的操作
	{
		r = p1->next;
		p1->next = L1->next;
		L1->next = p1;
		p1 = r;
	}
	return L1;
}

/*
	经过上一步操作后 所得到的链表中间以后的链表是逆置的
	运用奇偶链表的思想

	L--1--2--3--4--5--6
	
	L--1--2--3
	L1--6--5--4

	L--1--6--2--5--3--4
*/

void merge(LNode *&L)
{
	LNode *r, *s;
	LNode *L1 = divrev(L);
	LNode *p = L->next, *q = L1->next;
	L1->next = NULL;
	while (q != NULL)//奇数下面的链表短 偶数一样短 就让q!=NULL满足条件
	{
		r = p->next;
		s = q->next;
		p->next = q;
		q->next = r;
		p = r;
		q = s;
	}
}

int main24()
{
	LNode *L = bbbb();
	merge(L);
	L = L->next;
	while (L != NULL)
	{
		cout << L->data << " ";
		L = L->next;
	}
	return 0;
}