王道考研資料結構連結清單專題

王道後面的連結清單的代碼實作：

link.h

#pragma once
typedef int ElemType;
typedef char Element;

typedef struct Node {
	Element data;
	struct Node* next;
}Node,* Link;

//定義一個單連結清單結點
typedef struct LNOde
{
	ElemType data;
	struct LNOde* next;
}LNode, * LinkList;
//定義一個雙連結清單結點
typedef struct DNode {
	ElemType data;
	struct DNode* proir, * next;
}DNode, *DLinklist;
//定義一個Locate雙連結清單結點
typedef struct Dlnode {
	ElemType data;
	struct Dlnode* prior, * next;
	ElemType freg;	//表示調用頻度
}Dlnode, *DlocateList;

//數組尾插法建立單詞單連結清單
void listchar_RailInsert(Link& L, char arr[], int len);
//正向建立循環雙連結清單
void DlinkRailInsert(DLinklist& L ,int drr[], int len);
//數組尾插法建立單連結清單
void list_RailInsert1(LinkList& L, int arr[], int len);
//數組尾插法建立循環單連結清單
void list_RailInsertCycle(LinkList& L, int arr[], int len);
//周遊單連結清單
void arrayList(LinkList L);
//周遊輸出循環單連結清單
void arrListCycle(LinkList L);
//1.遞歸删除不帶頭節點的單連結清單
void del_value(LinkList& L,ElemType x);
//2.一遍順序掃描帶頭結點的單連結清單删除指定元素
void del_f(LinkList& L, ElemType x);
// 3. 反向輸出帶頭結點單連結清單的每個節點的值
void ouputData(LinkList L);
//4.編寫在帶頭結點的單連結清單L中删除一個最小節點的高效算法(假設最小節點值唯一)
void del_MinNode(LinkList& L);
void del_MinNode2(LinkList& L);
//5.将帶頭結點的單連結清單就地逆置(空間複雜度O(1))
void reverse(LinkList L);
//5.将帶頭結點的單連結清單就地逆置(空間複雜度O(1))
void reverse2(LinkList L);
//6.使帶頭節點的單連結清單元素遞增有序
void addOrderly(LinkList L);

//7.在無序連結清單中删除給定的範圍内元素的值
void del_values(LinkList& L, ElemType x, ElemType y);
// 7.在無序連結清單中删除給定的範圍内元素的值
void del_values2(LinkList & L, ElemType x, ElemType y);

//8.找出兩個單連結清單的公共節點
void findCommonNode(LinkList L1, LinkList L2);

//9.按遞增次序輸出單連結清單中各節點的資料元素，并釋放節點所占的存儲空間
void outputElement(LinkList L);

//10.将一個帶頭結點的單連結清單A分解為兩個帶頭結點的單連結清單A和B，使得A原奇，B原偶
LinkList resolve(LinkList &L);

//11.将線性表拆分為兩個單連結清單
LinkList decompose(LinkList &L);

//11.将線性表拆分為兩個單連結清單
LinkList decompose2(LinkList& A);

//12.設計算法删除遞增有序的單連結清單中出現的重複元素
void del_Element(LinkList& L);

//13.将兩個有序遞增單連結清單合并為遞減單連結清單，并利用原來兩個單連結清單的結點存放歸并後的單連結清單
LinkList combine(LinkList& L1, LinkList& L2);

//14.設計算法從遞增有序的單連結清單A和B中提取出公共元素産生單連結清單C，要求不破壞A、B結點
void extractCommon(LinkList L1, LinkList L2);

//15、兩個遞增有序的連結清單分别表示兩個集合，編寫函數求A、B交集存放于A集合中
void merge(LinkList& La, LinkList& Lb);

//16.判斷單連結清單B是否包含單連結清單B
int contain(LinkList& La, LinkList& Lb);

//17.設計一個算法用于判斷帶頭結點的循環雙連結清單是否對稱
int symmetry(DLinklist L);

//18. 合并兩個循環單連結清單，使合并後的連結清單仍保持循環單連結清單形式
void combine2(LinkList La, LinkList Lb);

//19.設計算法尋找帶頭結點的循環單連結清單的最小值輸出并删除，直到單連結清單為空，然後删除頭結點
void del_MinAll(LinkList& L);

//20.locate(L,X)函數的編寫 
void initlocate(DlocateList &L, int a[], int len);
//void locate(DlocateList L, int x);

//21.編寫算法求倒數第k個結點的值
int fundkValue(LinkList L,int k);

//22.找出單連結清單儲存的單詞具有相同的字尾的第一個單詞
void findCommon(Link La, Link Lb);

//23.删除重複元素值(包括絕對值)，隻保留第一個出現的元素
void delCommonValue(LinkList& L,int m);

//24.判斷一個連結清單是否有環，有環則輸出環的起始點
int isCycle(LinkList L);

//25.連結清單的重新排序
void resortLink(LinkList& L);
           

LinkPratice.cpp

#include<stdio.h>
#include<stdlib.h>
#include"link.h"


//數組尾插法建立單詞單連結清單
void listchar_RailInsert(Link& L, char arr[], int len) {
	L = (Link)malloc(sizeof(Node));//建立頭結點
	Node* s, * r = L;//r表示尾指針
	L->next = NULL;
	int i = 0;
	while (i < len) {
		s = (Node*)malloc(sizeof(Node));//建立一個新的節點
		s->data = arr[i++];
		r->next = s;
		r = s;
	}
	r->next = NULL;//尾指針置空;
	Node* p = L->next;
	while (p) {
		printf("%c", p->data);
		p = p->next;
	}
	printf("\n");
}
//數組尾插法建立單連結清單
void list_RailInsert1(LinkList& L,int arr[],int len) {
	int x;
	L = (LinkList)malloc(sizeof(LNOde));//建立頭結點
	LNOde* s, * r = L;//r表示尾指針
	L->next = NULL;
	
	int i = 0;
	while (i<len) {
		s = (LNOde*)malloc(sizeof(LNOde));//建立一個新的節點
		s->data = arr[i++];
		r->next = s;
		r = s;
	}
	r->next = NULL;//尾指針置空;

}

//數組尾插法建立循環單連結清單
void list_RailInsertCycle(LinkList& L, int arr[], int len) {
	int x;
	L = (LinkList)malloc(sizeof(LNOde));//建立頭結點
	LNOde* s, * r = L;//r表示尾指針
	L->next = NULL;

	int i = 0;
	while (i < len) {
		s = (LNOde*)malloc(sizeof(LNOde));//建立一個新的節點
		s->data = arr[i++];
		r->next = s;
		r = s;
	}
	r->next = L;//尾指針指向頭結點;
}

//指針顯示輸對外連結表
void arrayList(LinkList L) {
	LNOde* first;
	first = L->next;
	while (first) {
		printf("%d ", first->data);
		first = first->next;
	}
	printf("\n");
}

//正向建立循環雙連結清單(尾插法)
void DlinkRailInsert(DLinklist& L, int drr[], int len) {
	L = (DLinklist)malloc(sizeof(DNode));//建立循環連結清單頭結點
	DNode* r = L;	//尾指針
	L->next = NULL;
	for (int i = 0; i < len; i++)
	{
		int x = drr[i];
		DNode* s = (DNode*)malloc(sizeof(DNode));//每次建立結點
		s->data = x;
		r->next = s;
		s->proir = r;
		r = s;
	}
	r->next = L;
	L->proir = r;

	DNode* p = L->next;
	while (p != L) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

//1.遞歸删除不帶頭節點的單連結清單
void del_value(LinkList& L, ElemType x) {

	LNOde* p;//指向待删除的節點
	if (L == NULL) {
		return;			//遞歸的出口
	}
	if (L->data == x) {	//查找到值為x的L
		p = L;
		L = L->next;
		free(p);
		del_value(L, x);	//遞歸調用
	}
	else {				//若L指向的值不為x
		del_value(L->next, x);	 //遞歸調用
	}
}

//2.一遍順序掃描帶頭結點的單連結清單删除指定元素
void del_f(LinkList& L, ElemType x) {
	LNOde* head = L->next; LNOde* pre = L, * q;//聲明一個頭結點,維護一個前驅
	while (head) {
		if (head->data == x) {	//查找到要删除的元素
			q = head;
			head = head->next;
			pre->next = head;	//删除*q節點
			free(q);		 // 釋放*q節點的空間

		}
		else {
			head = head->next;
			pre = pre->next;
		}
	}
}

//3. 反向輸出帶頭結點單連結清單的每個節點的值
void ouputData(LinkList L) {
	//LNOde* p = L, temp;//指針p表示頭結點
	//LNOde* head = L->next;//頭指針
	//p->next = head;
	//if (L->next != NULL) {
	//	head = head->next;
	//}
	//if (L->next == NULL) {	//到達最尾部就輸出
	//	
	//	printf("%d ", L->data);
	//	ouputData(p);
	//}

	if (L->next != NULL) {		
		ouputData(L->next);
	}
	if (L != NULL) printf("%d ", L->data);
}

//4.編寫在帶頭結點的單連結清單L中删除一個最小節點的高效算法(假設最小節點值唯一)
void del_MinNode(LinkList& L) {
	LNOde* min = L->next; LNOde* head = L->next; LNOde* p;
	while (head) {
		if (head->data < min->data) {
			min = head;
		}
		head = head->next;
	}
	int x = min->data;//最小元素的值 
	while (head){
		if (head->data == x) {
			p = head->next;// p指向最小元素節點的下一個節點
			head->data = head->next->data;//交換元素
			head->next = p->next;//将最小元素斷鍊
			free(p);
		}
		head = head->next;
	}

}

//4.編寫在帶頭結點的單連結清單L中删除一個最小節點的高效算法(假設最小節點值唯一)
void del_MinNode2(LinkList& L) {
	LNOde* pre = L, * p = pre->next;	//表示目前節點的前驅指針和目前指針;
	LNOde* minpre = pre, * minp = p;//表示最小節點的前驅指針和最小指針;
	while (p!=NULL) {
		if (p->data < minp->data) {
			minpre = pre;
			minp = p;
		}
		pre = p;
		p = p->next;
	}
	minpre->next = minp->next;	//删除最小節點
	free(minp);
}

//5.将帶頭結點的單連結清單就地逆置(空間複雜度O(1))
void reverse(LinkList L) {
	LNOde* p, * s;
	p = L->next;
	L->next = NULL;
	while (p != NULL) {
		s = p->next;
		p->next = L->next ;
		L->next = p;
		p = s;
	}
}

//5.将帶頭結點的單連結清單就地逆置(空間複雜度O(1))
void reverse2(LinkList L) {
	LNOde* p, * r;	//p為工作指針，r為p的後繼，以防斷鍊
	p = L->next;	//從L的第一個元素開始
	L->next = NULL;	//先将L的next域置空
	while (p != NULL) {	//依次将節點摘下
		r = p->next;	//暫存p的後繼
		p->next = L->next;	//将p插入到頭結點之後
		L->next = p;
		p = r;
	}
}

//6.使帶頭節點的單連結清單元素遞增有序
void addOrderly(LinkList L) {
	LNode* p, * s;//表示目前工作指針和p的後繼
	p = L->next;
	L->next = NULL;
	while (p != NULL) {	//開始斷鍊
		s = p->next;
		
	}

}

//7.在無序連結清單中删除給定的範圍内元素的值
void del_values(LinkList &L,ElemType x,ElemType y) {
	LNOde* p = L->next, * s;//p表示工作指針,s表示指向p的後繼節點
	while (p) {
		if (p->data > x && p->data < y) {//找到符合條件的節點
			s = p->next;
			p->data = p->next->data;//将後繼節點的值複制給p，然後隻要删除s即可
			p->next->next = s->next;
			free(s);//釋放空間
		}
		else {
			p = p->next;
			s = p->next;
		}
	}
}

//7.在無序連結清單中删除給定的範圍内元素的值
void del_values2(LinkList& L, ElemType x, ElemType y) {
	LNOde* pre = L, * p = L->next;//表示目前節點的前驅和目前節點
	while (p) {
		if (p->data > x && p->data < y) {//找到符合條件的節點就删除
			pre->next = p->next;
			free(p);
			p = pre->next;
		}
		else {
			pre = p;
			p = p->next;
		}
	}
}

//8.找出兩個單連結清單的公共節點
void findCommonNode(LinkList L1, LinkList L2) {
	LNOde* L1head = L1->next, * L2head = L2->next;//分别指向L1和L2的第一個節點
	while (L1head) {
		while (L2head) {
			if (L2head->data == L1head->data) {
				printf("%d ", L2head->data);//相同就直接輸出
			}
			
				L2head = L2head->next;
			
		}
		L1head = L1head->next;		//L1指向下一個元素
		L2head = L2->next;			//每次比完後恢複原位
	}
}

//9.按遞增次序輸出單連結清單中各節點的資料元素，并釋放節點所占的存儲空間
void outputElement(LinkList L) {

}

//10.将一個帶頭結點的單連結清單A分解為兩個帶頭結點的單連結清單A和B，使得A原序号奇，B原序号偶
LinkList resolve(LinkList &A) {
	LinkList B; int count = 0;
	B = (LinkList)malloc(sizeof(LNOde));	//建立B表表頭
	B->next = NULL;		//初始化B表
	LNode* ra = A, *rb = B;			//ra和rb分别指向A和B的尾指針
	LNOde* p = A->next, * s;//p為工作指針
	A->next = NULL;//将A初始化
	while (p) {
		count++;
		//s = p->next;	//s為p的後繼
		if ((count & 1) == 0) {	// 序号偶數則存在B中
			rb->next = p;
			rb = p;
		}
		else {			// 序号奇數則存在A中
			ra->next = p;
			ra = p;
		}
		p = p->next;
	}
	ra->next = NULL; rb->next = NULL;
	return B;
}

//11.将線性表拆分為兩個單連結清單
LinkList decompose(LinkList &A) {
	LinkList B = (LinkList)malloc(sizeof(LNOde));	//建立B表頭
	B->next = NULL;		//B表初始化
	LNOde* b = B, * a = A;//a為表頭指針，b為表尾指針
	LNOde* p, * q;//p表示目前工作指針，q為p的後繼
	p = A->next;
	//A->next = NULL; // 将A初始化
	while (p) {
		//s = p->next;
		a->next = p; a = p;	//插入A中
		p = p->next;
		if (p != NULL) {
			q = p->next;
			p->next = b->next;	//尾插法插入B中
			b->next = p;
			p = q;
		}
	}
		a->next = NULL;
		return B;
	}

//11.将線性表拆分為兩個單連結清單
LinkList decompose2(LinkList& A) {
	int count = 0;
	LinkList B = (LinkList)malloc(sizeof(LNOde));	//建立B表頭
	B->next = NULL;		//B表初始化
	LNOde* b = B, * a = A;//a為表頭指針，b為表尾指針
	LNOde* p, * q;//p表示目前工作指針，q為p的後繼
	p = A->next;
	A->next = NULL; // 将A初始化
	while (p) {
		count++;
		q = p->next;	//q為p的後繼
		if ((count & 1) == 1) {
			a->next = p;
			a = p;	//插入A中
		}
		else {
			p->next = b->next;//尾插法插入B中
			b->next = p;
		}
		p = q;
	}
	a->next = NULL;
	return B;
}

//12.設計算法删除遞增有序的單連結清單中出現的重複元素
void del_Element(LinkList &L) {
	LNOde* slow = L->next, * fast,*p;//設定快慢指針,p為暫時指針
	while (slow->next!=NULL) {
		fast = slow->next;
		if (fast->data == slow->data) {	//相等則表示有相同的元素
			slow->next = fast->next;
			p = fast;
			free(p);
		}
		else {
			slow = slow->next;
		}
		
	}
}

//13.将兩個有序遞增單連結清單合并為遞減單連結清單，并利用原來兩個單連結清單的結點存放歸并後的單連結清單
LinkList combine(LinkList &L1, LinkList& L2) {
	LNOde* La = L1->next, * Lb = L2->next, *p;//La和Lb分别表示兩個連結清單的第一個結點，p為工作指針
	L1->next = NULL; //将L1設定為目前合成的新連結清單;
	while (La && Lb) {//先找出兩個連結清單的公共部分
		if (La->data <= Lb->data) {	//比較元素
			p = La->next;	//暫存La的後繼結點
			La->next = L1->next;
			L1->next = La;

			La = p;	//La繼續往下走
		}
		else {
			p = Lb->next;//暫存Lb的後繼結點
			Lb->next = L1->next;
			L1->next = Lb;

			Lb = p;//Lb繼續往下走
		}

	}
	if (La) {	//L1有剩餘
		Lb = La;
	}
	while (Lb) {	//一起處理
		p = Lb->next;//暫存Lb的後繼結點
		Lb->next = L1->next;
		L1->next = Lb;

		Lb = p;//Lb繼續往下走
	}
	free(L2);
	return L1;
}

//14.設計算法從遞增有序的單連結清單A和B中提取出公共元素産生單連結清單C，要求不破壞A、B結點
void extractCommon(LinkList L1, LinkList L2) {
	LNOde* La = L1->next, * Lb = L2->next,*r;
	LinkList C = (LinkList)malloc(sizeof(LNOde));//建立新表C
	r = C; //r始終指向C的尾結點
	while (La && Lb) {
		if (La->data < Lb->data) {	//小于的話La向後移一位
			La = La->next;
		}
		else if (La->data > Lb->data) {
			Lb = Lb->next;
		}
		else {			//相等則一起向後移一位
			LNOde* s = (LNOde*)malloc(sizeof(LNOde));//建立一個新的結點
			s->data = La->data;
			r->next = s;
			r = s;
			La = La->next;
			Lb = Lb->next;
		}
	}
	r->next = NULL;
	arrayList(C);
}

//15、兩個遞增有序的連結清單分别表示兩個集合，編寫函數求A、B交集存放于A集合中
void merge(LinkList& La, LinkList& Lb) {
	LNOde* pa = La->next, * pb = Lb->next, * pc = La,*temp;// pa,pb分别表示工作指針，pc指向La的頭結點
	while (pa && pb) {
		if (pa->data == pb->data) {	//元素相等就加入pa
			pc ->next = pa;
			pc = pa;
			pa = pa->next;
			temp = pb;	//将pb中的結點釋放
			pb = pb->next;
			free(temp);	//釋放結點temp
		}
		else if (pa->data < pb->data) {
			temp = pa;
			pa = pa->next;
			free(temp);//釋放結點temp
		}
		else {
			temp = pb;
			pb = pb->next;
			free(temp);//釋放結點temp
		}
	}
	while (pa) {//while循環結束後，如果La中還有剩餘則周遊
		temp = pa;
		pa = pa->next;
		free(temp);//釋放結點temp
	}
	while (pb) {//while循環結束後，如果Lb中還有剩餘則周遊
		temp = pb;
		pb = pb->next;
		free(temp);//釋放結點temp
	}
	pc->next = NULL;
	free(Lb);
	arrayList(La);
}

//16.判斷單連結清單B是否包含單連結清單B
int contain(LinkList& La, LinkList& Lb) {
	LNOde* pa = La->next, * pb = Lb->next, * pre = pa;//pa和pb分别表示工作指針
	while (pa && pb) {
		if (pa->data == pb->data) {
			pa = pa->next;
			pb = pb->next;
		}
		else {
			pre = pre->next;	//A從下一個元素開始
			pa = pre;
			pb = Lb->next;		// B每次從頭開始
		}
	}
	if (pb == NULL) {	//判斷pb是否能比較完了
		return 1;
	}
	return 0;
}

//17.設計一個算法用于判斷帶頭結點的循環雙連結清單是否對稱
int symmetry(DLinklist L) {
	//從兩邊掃描循環雙連結清單，判斷是否對稱
	DNode* p = L->next, *q = L->proir;
	while (p != q && q->next != p) {
		if (p->data == q->data) {
			p = p->next;
			q = q->proir;
		}
		else {
			return 0;
		}
	}
	return 1;
}

//18. 合并兩個循環單連結清單，使合并後的連結清單仍保持循環單連結清單形式
void combine2(LinkList La, LinkList Lb) {
	LNOde* h1 = La, * h2 = Lb, * p = Lb->next;//h1和h2分别指向循環單連結清單的頭結點
	Lb->next = NULL;//斷鍊Lb
	while (h1->next != La) {
		h1 = h1->next;
	}
	h1->next = p;
	while (h1->next != Lb) {
		h1 = h1->next;
	}
	h1->next = La;
	arrListCycle(La);
}

//周遊輸出循環單連結清單
void arrListCycle(LinkList L) {
	LNOde* f = L->next;
	while (f && f != L) {
		printf("%d ", f->data);
		f = f->next;
	}
	printf("\n");
}

//19.設計算法尋找帶頭結點的循環單連結清單的最小值輸出并删除，直到單連結清單為空，然後删除頭結點
void del_MinAll(LinkList& L) {
	while (L->next != L) {	//當連結清單不為空時一直循環
		LNOde* p = L->next, * pre = L, *minp=p,*minpre=pre;	//p為工作指針，pre為p的前驅
		while (p != L) {
			if (minp->data > p->data) {
				minp = p;	//min指向最小元素
				minpre = pre;
			}
			pre = p;
			p = p->next;
		}
		printf("%d ", minp->data);//輸出最小元素
		minpre->next = minp->next;//删除最小值指針結點
		free(minp);
	}
	free(L);
}

//尾插法建立locate雙連結清單
void initlocate(DlocateList &L,int a[],int len) {
	L = (DlocateList)malloc(sizeof(Dlnode));//建立雙連結清單頭結點
	Dlnode* s, * r;//r為尾指針
	r = L;
	int i = 0;
	while (i<len) {
		s = (Dlnode*)malloc(sizeof(Dlnode));//建立結點
		s->data = a[i++];//指派
		s->freg = 0;
		r->next = s;//插入
		s->prior = r;
		r = s;
	}
	r->next = NULL;
	Dlnode *p = L->next;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
}
//20.locate(L,X)函數的編寫 
//void locate(DlocateList L, int x) {
//	Dlnode* p = L->next, * pre=L;//p第一個工作指針,temp為臨時指針
//	while (p) {
//		if (p->data == x) {	//找到相同結點時，freg加一 
//			p->freg++;	//同時插入到頭結點後面
//
//			pre->next = p;
//			pre->next = p->next;	//删除節點temp 
//			p->next->prior=p->prior;
//			//然後插入到頭結點後面即可
//			Dlnode* s = (Dlnode*)malloc(sizeof(Dlnode));
//			s->data = x;
//			s->next = L->next;
//			L->next->prior = s;
//			L->next = s;
//			s->prior = L;
//		}
//		p = p->next;
//	}
//	Dlnode* p = L->next;
//	while (p) {
//		printf("%d ", p->data);
//		p = p->next;
//	}
//	printf("\n");
//}

//21.編寫算法求倒數第k個結點的值
int fundkValue(LinkList L,int k) {
	LNOde* list = L, * slow = list->next,*temp=list->next, * fast;	//list為頭指針
	while (k-- >0 && temp!=NULL) {
		temp = temp->next;
	}
	if (k > 0) {
		return 0;
	}
	else {
		fast = temp;
		while (fast) {
			slow = slow->next;
			fast = fast->next;
		}
		printf("輸出的倒數第%d 個結點的值為%d \n",k, slow->data);
		return 1;
	}
	
}

//22.找出單連結清單儲存的單詞具有相同的字尾的第一個單詞
void findCommon(Link La, Link Lb) {
	Node* p = La->next, * q = Lb->next,*s1=La->next,*s2=Lb->next;//str1和str2分别是La和Lb的第一個結點
	int count1 = 0, count2 = 0;
	while (p) {
		count1++;
		p = p->next;
	}
	while (q) {
		count2++;
		q = q->next;
	}
	int temp =count1-count2;
	while (temp-- > 0) {
		s1 = s1->next;
	}
	while (s1 && s2) {
		if (s1->data == s2->data) {
			printf("%c", s1->data);
			return;
		}
		else {
			s1 = s1->next;
			s2 = s2->next;
		}
	}
	printf("\n");
}

//23.删除重複元素值(包括絕對值)，隻保留第一個出現的元素
void delCommonValue(LinkList& L, int n) {
	LNOde* p = L, * r;
	int* q, m;
	q = (int*)malloc(sizeof(int) * (n + 1));	//申請n+1個位置的輔助空間
	for (int i = 0; i < n + 1; i++){
		*(q + i) = 0;				//數組元素初始值指派0
	}
		while (p->next != NULL) {//周遊單連結清單元素
			m = p->next->data > 0 ? p->next->data : -p->next->data;	//判斷元素的正負
			if (*(q + m) == 0) {	//判斷該節點的data是否出現過
				*(q + m) = 1;		//第一次出現
				p = p->next;		//保留
			}
			else {					//重複出現則删除
				r = p->next;
				p->next = r->next;
				free(r);
			}
		}
	free(q);
	arrayList(L);
}

//24.判斷一個連結清單是否有環，有環則輸出環的起始點
int isCycle(LinkList L) {
	LNOde* slow = L->next, * fast = L->next;	//設定快慢指針
	while (slow != NULL&&fast->next!=NULL) {
		fast = fast->next->next;	//快指針每次走兩步
		slow = slow->next;		//慢指針每次走一步
		if (fast == slow) {
			return fast->next->data;	//如果快慢指針相同則一定有環且下一個指針即為出口
		}
	}
	return 0;
}

//25.連結清單的重新排序
void resortLink(LinkList& L) {
	
}
           

LinkTest.cpp

#include<stdio.h>
#include"link.h"
int  main() {
    LinkList link, link1, link3, link4,link5; DlocateList dlocate; Link charlink,charlink1;
    DLinklist Dlink;
    int arr[] = {1,2,3,4,5,6,7};
    int arr2[] = {3,4,5,7};
    int len = sizeof(arr) / sizeof(int);
    int len2 = sizeof(arr2) / sizeof(int);
    list_RailInsert1(link,arr,len);
    list_RailInsert1(link1, arr2, len2);
    printf("尾插法建立的單連結清單為：\n");
    arrayList(link); arrayList(link1);
    printf("遞歸删除後的單連結清單為：\n");
    del_value(link,2);//1.遞歸删除元素
    del_f(link,2);//2.一遍順序掃描删除指定元素
    arrayList(link);
    ouputData(link);//3. 反向輸出帶頭結點單連結清單的每個節點的值
    printf("\n");
    printf("删除最小節點元素後的單連結清單為：\n");
    del_MinNode(link);//4.編寫在帶頭結點的單連結清單L中删除一個最小節點的高效算法(假設最小節點值唯一)
    arrayList(link);
    del_MinNode2(link);
    arrayList(link);
    //将帶頭結點的單連結清單就地逆置(空間複雜度O(1))
     printf("單連結清單就地逆置後為：\n");
     reverse(link); arrayList(link);
     reverse2(link); arrayList(link);
     printf("删除指定區間後的元素為：\n");
     del_values2(link, 2, 5); arrayList(link);
     printf("尾插法建立的單連結清單2為：\n");
    // list_RailInsert(link1);
     printf("輸出兩個連結清單相同的元素：\n");
     findCommonNode(link, link1);
     printf("遞增輸出單連結清單中的各元素：\n");
     outputElement(link);
     printf("輸出分解後的兩個單連結清單為：\n");
     /*link3 = resolve(link);
     arrayList(link3);
     arrayList(link);*/
     /*printf("變換後的兩個單連結清單分别為：\n");
     link3 = decompose(link); arrayList(link3);
     arrayList(link);*/
     printf("輸出删除重複元素後的單連結清單為：\n");
     del_Element(link);  arrayList(link);
     printf("輸出合并後的單連結清單為：\n");
     arrayList(combine(link,link1));
     /*printf("輸出兩個連結清單的公共元素為：\n");
     extractCommon(link, link1);
     printf("輸出歸并後的單連結清單為：\n");
     merger(link, link1);*/
     printf("輸出單連結清單A中是否包含單連結清單B的結果：\n");
     printf("%d \n",contain(link, link1));
     int drr[] = {1,2,1};
     int dlen = sizeof(drr) / sizeof(int);
     printf("建立的循環雙連結清單為： \n");
     DlinkRailInsert(Dlink,drr,dlen);
     printf("輸出的結果為：%d \n", symmetry(Dlink));
     printf("合并後的循環單連結清單為：\n");
     int dlink[] = { 1,2,3 }; int lend1 = sizeof(dlink) / sizeof(int);
     int dlink2[] = { 4,5,6 }; int lend2 = sizeof(dlink2) / sizeof(int);
     list_RailInsertCycle(link3, dlink, lend1);
     list_RailInsertCycle(link4, dlink2, lend2);
     combine2(link3, link4); printf("\n");
     LinkList minlist;
     int min[] = { 3,2,4,6,9,2 };
     int lenmin = sizeof(min) / sizeof(int);
     list_RailInsertCycle(minlist, min, lenmin);
     printf("插入後的循環單連結清單為：\n"); arrListCycle(minlist);
     printf("輸出依次找到的最小值為：\n");
     del_MinAll(minlist);
     printf("\n");
     printf("輸出建立的雙連結清單為：\n");
     int a[] = {1,4,6,7,9,5};
     int le = sizeof(a) / sizeof(int);
     initlocate(dlocate,a,le);//建立locate雙連結清單
     printf("\n");
     printf("輸出雙連結清單按頻度通路節點的所有元素：\n");
     //locate(dlocate, 6);
     printf("輸出倒數第k個結點的值：\n");
     printf("傳回的結果為：%d\n", fundkValue(link, 1));
     printf("插入的兩個單詞單連結清單為：\n");
     char ch[] = {'l','o','d','o','i','n','g'};
     int chlen = sizeof(ch) / sizeof(char);
     char ch1[] = { 'b','e','o','i','n','g' };
     int chlen1 = sizeof(ch1) / sizeof(char);
     listchar_RailInsert(charlink, ch, chlen);
     listchar_RailInsert(charlink1, ch1, chlen1);
     printf("輸出的兩個單連結清單的第一個相同的字尾字母為：\n");
     findCommon(charlink,charlink1);
     int del[] = { -2,-2,-3,3,4,5,7,-7 };
     int dellen = sizeof(del) / sizeof(int);
     list_RailInsert1(link5, del, dellen);
     printf("建立的單連結清單為：\n"); arrayList(link5);
     printf("輸出删除絕對值相同的元素後的單連結清單為：\n");
     delCommonValue(link5,7);
     printf("判斷連結清單是否有環：%d", isCycle(link5));
}