单链表

2023-09-08   

单链表结构定义

typedef struct LNode {
	ElemType data; 	//节点数据域
	struct LNode *next;	//节点指针域
} LNode, *LinkList; 	//LinkList为指向struct LNode的指针


LinkList L; //定义链表L 
LNode *p;   //定义节点指针

初始化

void initList(LinkList &L)
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
}

单链表基本操作

头插法建立单链表

每次插入到头结点后，即顺序输入是逆序输出，一般用于链表逆置。
头插

LinkList list_HeadInsert() {
	LinkList L;
	LNode *p;
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	scanf("%d", &x);
	while(x != 9999) {
		p = (LNode*)malloc(sizeof(LNode));
		p->data = x;
		p->next = L->next;
		L->next = p;
		scanf("%d", &x); 
	}
	return L;
}

尾插法建立单链表

初始建立一个尾指针r，每次将尾指针更新成插入后的结点。
尾插

LinkList list_TailInsert() {
	LinkList L;
	LNode *p, *r;
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	r = L; 
	scanf("%d", &x);
	while(x != 9999) {
		p = (LNode *)malloc(sizeof(LNode));
		p -> data = x;
		r -> next = p;
		r = p;
		scanf("%d", &x);
	}
	r -> next = NULL;
	return L; 
}

单链表查找

//按序号查找
LNode *getElem(LinkList L, int i) {
	if (i < 1)	return NULL;
	int j = 1;
	LNode *p = L -> next;
	while(p != NULL && j < i) {
		p = p -> next;
		j ++;
	}
	return p;
} 

//按值查找
LNode *locateElem(LinkList L, int x) {
	LNode *p = L -> next;
	while(p != NULL && p->data != x) {
		p = p -> next;
	}
	return p;
}

单链表插入

void insertNode(LinkList &L, LNode *s, int pos) {
	LNode *pre = getElem(L, pos - 1);
	s -> next = pre -> next;
	pre -> next = s;
}

单链表删除

void deleteNode(LinkList &L, int pos) {
	LNode *pre = getElem(L, pos - 1);
	LNode *q = pre -> next;
	pre->next = q->next;
	free(q);
}

单链表表长

int getLength(LinkList L) {
	int cnt = 0;
	for (LNode *p = L -> next; p != NULL; p = p -> next) {
		cnt ++;
	}
	return cnt;
}

单链表相关题目

题意：
设计一个递归算法，删除不带头结点的单链表L中的说有值为x的节点
思路：
直接按题意递归。

void del(LinkList &L, int x) {
	LNode *p;
	if (L == NULL) {
		return ;
	}
	if (L -> data == x) {
		p = L;
		L = L -> next;
		free(p);
		del(L, x);
	} else {
		del(L -> next, x);
	}
}

题意：
在带头节点的单链表L中，删除所有值为x的结点，并释放空间，假设值为x的结点不唯一。
思路
记录前驱，当前结点是x时删除即可。

void delNum(LinkList &L, int x) {
	LNode *p = L -> next, *pre = L, *q;
	while(p != NULL) {
		if (p -> data == x ) {
			q = p;
			p = p -> next;
			pre -> next = p;
			free(q);
		} else {
			pre = p;
			p = p -> next;
		}
	}
}

题意：
设L为带头节点的单链表， 编写算法实现从尾到头反向输出每个节点的值。
思路
递归输出。

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

题意：
试编写在带头节点的单链表L中删除一个最小值结点（最小值唯一）的高效算法。
思路
记录最小值和最小前驱，最后删除最小值。

void del_Min(LinkList &L) {
	LNode *pre = L, *p = pre -> next;
	LNode *minpre = pre, *minp = p;
	while(p != NULL) {
		if (p -> data < minp -> data) {
			minp = p;
			minpre = pre;
		}
		pre = p;
		p = p -> next;
	}
	minpre -> next = minp -> next;
	free(minp);
}

题意：
试编写算法将带头结点的单链表就地逆置。
思路
使用链表前插法即可。

void list_Reverse(LinkList &L) {
	LNode *p, *r;
	p = L -> next;
	L -> next = NULL;
	while(p != NULL) {
		r = p -> next;  //保留后面结点
		p -> next = L -> next;
		L -> next = p;
		p = r;	//恢复后续
	}
}

题意：
有一个带头结点的单链表L，设计一个算法使其元素递增排列。
思路
使用插入排序即可。

void insertSort(LinkList &L) {
	LNode *p = L -> next, *pre;
	LNode *r = p -> next;	//保存p的后继指针，不断链 
	p -> next = NULL;	//初始化只保留一个数据结点 
	p = r;
	while(p != NULL) {
		r = p -> next;
		pre = L;	// 每次进行插入排序，pre重置头结点
		while(pre->next != NULL && pre->next->data < p->data) {
			pre = pre -> next;
		}
		p -> next = pre -> next;
		pre -> next = p;
		p = r;
	}
}

题意：
设计一个带头结点的单链表L中所有元素结点的数据值无序，删除表中介于给定两个值之间的所有元素。
思路
遍历一遍，符合条件删除即可。

void rangeDel(LinkList &L, int min, int max) {
	LNode *pre = L, *p = L -> next;
	while(p != NULL) {
		if (p -> data > min && p -> data < max) {
			pre -> next = p -> next;
			free(p);
			p = pre -> next;
		} else {
			pre = p;
			p = p -> next;		
		}
	}
}

题意：
给定两个单链表，编写算法找到两个链表的公共结点
思路
先分别遍历两个链表得到长度，求出长度之差，在长的链表上先遍历长度之差个节点后，两个链表同步遍历，直到找到公共结点。

LinkList searchCommon(LinkList L1, LinkList L2) {
	int len1 = getLength(L1);
	int len2 = getLength(L2);
	int lenDis = abs(len1 - len2);
	LinkList longList, shortList;
	if (len1 > len2) {
		longList = L1 -> next;
		shortList = L2 -> next;
	} else {
		shortList = L2 -> next;
		longList = L1 -> next;
	}
	while(lenDis --)	
		longList = longList -> next;
	while(longList != NULL) {
		if (longList == shortList)
			return longList;
		else {
			longList = longList -> next;
			shortList = shortList -> next;
		}
	}
	return NULL;	
}

题意：
给定一个带头结点的单链表，按递增次序输出单链表中各结点的数据元素，并释放结点空间。
思路
对链表进行遍历，每次遍历找到链表的最小值元素，输出并释放空间，再查找次小值元素，并释放空间，如此循环，直至链表为空。

void min_Del(LinkList &L) {
	while(L -> next != NULL) {	//循环到只剩头结点
		LNode *pre = L;		//pre为元素最小值结点的前驱结点指针
		LNode *p = pre -> next;	//	工作指针
		LNode *q;	//指向被删除指针
		while(p -> next != NULL) {	//找到最小值的前驱
			if (p -> next -> data < pre -> next -> data)
				pre = p;
			p = p -> next;
		}
		printf("%d ", pre -> next -> data);
		q = pre -> next;
		pre -> next = q -> next;	//删除最小值
		free(q);
	}
	free(L);
}

题意：
将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，B表中含有原表序号为偶数的元素，且保持相对顺序不变。
思路
遍历，判断奇偶性，分别插入。

LinkList discreat(LinkList &A) {
	int i = 0;
	LinkList B = (LinkList)malloc(sizeof(LNode));
	B -> next = NULL;
	LNode *ra = A, *rb = B, *p;
	
	p = A -> next;
	A -> next = NULL;
	while(p != NULL) {
		i ++;
		if (i % 2 == 0) {
			rb -> next = p;
			rb = p;
		} else {
			ra -> next = p;
			ra = p;
		}
		p = p -> next;
	}
	ra -> next = NULL;
	rb -> next = NULL;
	return B;
}

题意：
设C=a1,b1,a2,b2...an,bnC=a_1,b_1,a_2,b_2...a_n,b_n为线性表，采用带头结点单链表存储，设计一个就地算法，将其拆分为两个线性表，使得A=a1,a2...anA=a_1,a_2...a_n,B=bn,bn−1...b1B=b_n,b_{n-1}...b_1
思路
基本同上一题，只是B表插入换成头插法

LinkList discreat2(LinkList &A) {
	LinkList B = (LinkList)malloc(sizeof(LNode));
	B -> next = NULL;
	LNode *p = A -> next, *q;
	LNode *ra = A;
	while(p != NULL) {
		ra -> next = p;
		ra = p;
		p = p -> next;
		if (p != NULL) {
			q = p -> next;
			p -> next = B -> next;
			B -> next = p;
			p = q;
		}
	}
	ra -> next = NULL;
	return B;
}

题意：
去除递增有序单链表中重复元素
思路
遍历判断。

void delSame(LinkList &L) {
	LNode *p = L -> next, *q;
	if (p == NULL)	return ;
	while(p -> next != NULL) {
		q = p -> next;
		if (p -> data == q -> data) {
			p -> next = q -> next;
			free(q);
		} else {
			p = p -> next;
		}
	}
}

题意：
将两个递增有序的单链表合并为递减的单链表，并利用原来两个单链表的结点存放合并后的单链表。
思路
因为原链表递增有序，故从第一个结点开始比较，将小的结点链入链表，同时后移工作指针。（头插链入，这样得到的就是递减链表）比较结束后，如果某个链表非空，则将剩下的直接链入。

void MergeList(LinkList &A, LinkList &B) {
	LNode *pa = A -> next, *pb = B -> next, *q;
	A -> next = NULL;
	
	while(pa && pb) {
		if (pa -> data <= pb -> data) {
			q = pa -> next;
			pa -> next = A -> next;
			A -> next = pa;
			pa = q;
		} else {
			q = pb -> next;
			pb -> next = A -> next;
			A -> next = pb;
			pb = q;
		}
	}	
	if (pa)	//处理非空链表
		pb = pa;
	while(pb) {
		q = pb -> next;
		pb -> next = A -> next;
		A -> next = pb;
		pb = q; 
	}
	free(B);
}

题意：
设A和B是两个递增单链表（带头结点），从A和B中公共元素产生单链表C，不破坏A，B的结点。
思路
从头开始依次比较，如果不等，值小的后移，如果相等，尾插法链入新的链表中。直至一个链表遍历到表尾。

LinkList getCommon(LinkList A, LinkList B) {
	LNode *pa = A -> next, *pb = B -> next, *r, *s;
	LinkList C = (LinkList)malloc(sizeof(LNode));
	C -> next = NULL;
	r = C;
	while(pa && pb) {
		if (pa -> data < pb -> data) {
			pa = pa -> next;
		} else if (pa -> data > pb -> data) {
			pb = pb -> next;
		} else {
			s = (LNode*)malloc(sizeof(LNode));
			s -> data = pa -> data;
			r -> next = s;
			r = s;
			pa = pa -> next;
			pb = pb -> next;
		}
	}
	r -> next = NULL;
	return C;
}

题意：
已知两个链表A和B，两个集合，递增排列，求A和B的交集，并存放于A中。
思路
设置两个工作指针pa和pb，对两个链表进行扫描，只有同时出现在两集合中的元素才链接到结果表中且只保留一个，其他结点全部释放，当一个链表遍历完毕后，释放另一个剩下链表的全部结点。

void unionList(LinkList &A, LinkList &B) {
	LNode *pa = A -> next, *pb = B -> next;
	LNode *r = A, *u;
	
	while(pa && pb) {
		if (pa -> data < pb -> data) {
			u = pa;
			pa = pa -> next;
			free(u);
		} else if (pa -> data > pb -> data) {
			u = pb;
			pb = pb -> next;
			free(u);
		} else {
			r -> next = pa;
			r = pa;
			pa = pa -> next;
			u = pb;
			pb = pb -> next;
			free(u);
		}
	}
	while(pa) {
		u = pa;
		pa = pa -> next;
		free(u);
	}
	while(pb) {
		u = pb;
		pb = pb -> next;
		free(u);
	}
	r -> next = NULL;
	free(B);
}

题意：
两个整数序列A和B存在单链表中，判断B是否是A的连续子序列。
思路
从两个链表的第一个结点开始，若相等，则后移，若不等，则A链表从从上次开始比较结点的后继开始，B链表仍从第一个结点开始比较。直至B链表到表尾表示匹配成功。

bool judge(LinkList A, LinkList B) {
	LNode *pa = A -> next, *pb = B -> next;
	LNode *pre = pa;
	
	while(pa && pb) {
		if (pa -> data == pb -> data) {
			pa = pa -> next;
			pb = pb -> next; 
		} else {
			pre = pre -> next;
			pa = pre;
			pb = B -> next; 
		}
	}
	return pb == NULL ? true : false; 
}

题意：
判断单链表是否存在有环
思路
设置快慢两个指针，slow慢指针每次走一步，fast快指针每次走两步，如果有环，则fast一定先进入环，slow后进入环，当两个指针都进入环后，经过若干操作一定能确定链表是否有环。
环的入口点：头结点和快慢指针相遇点同步移动，两者相遇即为切入。

LNode *findLoop(LNode *L) {
	LNode *fast = L -> next, *slow = L -> next;
	while(fast != NULL && fast -> next != NULL) {
		slow = slow -> next;
		fast = fast -> next -> next;
		if (slow == fast)
			break;
	}
	if (fast == NULL || fast -> next == NULL)
		return NULL;
	LNode *p1 = L -> next;
	LNode *p2 = slow;
	while(p1 != p2) {
		p1 = p1 -> next;
		p2 = p2 -> next;
	}
	return p1;	//入口点 
}

题意：
一个带头结点的单链表，只给出了头指针list，在不改变链表的前提下，查找链表中倒数第K个位置上的结点。
思路
设置两个指针，一个先走k步，之后同步走，当先走的到达表尾时，慢指针此时所指向的即时所求结点。

int searchK(LinkList list, int k) {
	LNode *p = list -> next;
	LNode *q = list -> next;
	int cnt = 0;
	while (p != NULL) {
		if (cnt < k)	cnt ++;
		else	q = q -> next;
		p = p -> next; 
	} 
	if (cnt < k)	return 0;	//k比链表长度还长，不合法
	else {
		printf("%d\n", q -> data);
		return 1;
	}
}

题意：
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间，设str1和str2分别指向两个单词所在单词单链表所在的头结点，找出由str1和str2所指向两个链表共同后缀的起始位置。
思路
首先求出str1和str2的长度分别为m,n。将两个链表表尾对齐，即m>=n时，str1的指针先移动至m-n+1结点，反之则移动至n-m+1。当两个链表表尾长度相同时，同时移动，直至两个指针指向同一位置即停止。

LNode* find_addr(LinkList str1, LinkList str2) {
	int m = getLength(str1);
	int n = getLength(str2);
	LNode *p, *q;
	for (p = str1; m > n; m --)
		p = p -> next;
	for (q = str2; n > m; n --)
		q = q -> next;
	while(p -> next != NULL && p -> next != q -> next) {
		p = p -> next;
		q = q -> next;
	}
	return p -> next;
}

题意：
用单链表保存m个整数，结点数据绝对值小于等于n，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。
思路
主要使用一个辅助数组，记录链表中已出现的数值。
扫描一遍链表，按题意操作即可。

void delAbs(LinkList &L, int n) {
	LNode *p = L, *r;
	int *vis = (int *)malloc(sizeof(int)*(n + 1));
	for (int i = 0; i < n + 1; i ++)
		*(vis + i) = 0;
	while(p -> next != NULL) {
		int m = p -> next -> data > 0 ? p -> next -> data : -p -> next -> data;
		if (*(vis + m) == 0) {
			*(vis + m) = 1;
			p = p -> next;
		} else {
			r = p -> next;
			p -> next = r -> next;
			free(r);
		}
	}
}

题意：
设L=a1,a2,a3,...an−2,an−1,anL=a_1,a_2,a_3,...a_{n-2},a_{n-1},a_{n}为线性表，采用带头结点单链表存储，设计算法，将其变为L=a1,an,a2,an−1,a3,an−2...L=a_1,a_n,a_2,a_{n-1},a_3,a_{n-2}...
思路
先找出链表的中间结点，设置p,q指针，p每次走一步，q每次走两步，当q到达结尾是，p指向中间结点。然后将L的后半段结点逆置，单链表从前后两段依次插入即可。

void changeList(LinkList &L) {
	LNode *p, *q, *r, *s;
	p = q = L;
	while(q -> next != NULL) {	//寻找中间结点
		p = p -> next;
		q = q -> next;
		if (q -> next != NULL)
			q = q -> next;
	}
	q = p -> next;	//此时p所指向中间结点
	p -> next = NULL;	//断开分成两段
	while(q != NULL) {	//	后半段逆置
		r = q -> next;
		q -> next = p -> next;
		p -> next = q;
		q = r;
	}
	s = L -> next;	//指向前半段第一个
	q = p -> next;	//指向后半段第一个
	p -> next = NULL;
	while(q != NULL) {	//将链表后半段的结点插入到指定位置，前插法
		r = q -> next;	
		q -> next = s -> next;	
		s -> next = q;
		s = q -> next;
		q = r;
	}
}

Q.E.D.