数据结构代码题-链表

愷龍

发布于 2023-10-16 15:56:04

3380

发布于 2023-10-16 15:56:04

文章被收录于专栏：愷龍的Blog愷龍的Blog

链表

单链表

单链表结构体的声明：

typedef struct Link {
	int data;//代表数据域
	struct Link* next;// 代表指针域，指向直接后继元素
} link; //link为节点名，每个结点都是一个link结构体

另一种：

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

求单链表长度函数：

int getListLength(LinkList*list)
{
    int n=0;
    LinkList*p=list;
    while(p->next!=NULL)
    {
    n++;
    p=p->next;
    }
    return n;
}

带头结点的单链表初始化：

link* initLink() {
	link * p = (link*)malloc(sizeof(link)); //创建一个头结点
	link * temp = p; //声明一个指针指向头结点，
	//头结点的数据域内没有东西 指针域内指向第一个数据域内有东西的结点
	//生成链表
	int acc = 0;
	printf("请输入你想输入的元素个数：\n");
	scanf("%d",&acc);
	printf("请输入每个元素的值：\n");
	for(int i = 0;i < acc;i++){
		int num = 0;
		scanf("%d",&num);
		link* a = (link*)malloc(sizeof(link)); //每一个for循环创建一个结点
		a->data = num;
		a->next = NULL; //结点的指针域为空
		temp->next = a; //temp结点的next为新创建的结点
		temp = temp->next; //完成上一步后让最新的结点就是temp结点
	}
	return p;
}

尾插法建立单链表：

LinkList CreateList_Tail(LinkList L)
{
	int x;
	L = (LNode*)malloc(sizeof(LNode));
	LNode *s,*r=L;
	scanf("%d",&x);
	while(x!=9999){                             
		s=(LNode*)malloc(sizeof(LNode));     //创建新的结点 
		s->Data=x;                           
		r->Next=s;                      
		r=s;
		scanf("%d",&x);
	}
	r->Next=NULL;
	return L;
 }

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

#include <stdio.h>
#include <stdlib.h>
typedef struct SqNode {
	int data;
	struct  SqNode* Next;
} SqNode, *SqList;
SqList CreateList(SqList L) {
	L = (SqList)malloc(sizeof(SqNode));
	SqList s;
	SqList r;
	int Value = 0;
	printf("请输入您需要创建的链表,以999结束输入\n");
	scanf_s("%d", &Value);
	getchar();
	L->data = Value;
	L->Next = NULL;
	r = L;
	scanf_s("%d", &Value);
	getchar();
	while (Value != 999) {
		s = (SqList)malloc(sizeof(SqNode));
		s->data = Value;
		s->Next = r->Next;
		r->Next = s;
		r = s;
		scanf_s("%d", &Value);
		getchar();
	}
	return L;

}
//创建链表
SqList DeleteElement(SqList *L, int Value) {
	SqList s;
	if (*L == NULL) {
		return;
	}
	if ((*L)->data == Value ) {
		s = *L;
		*L = (*L)->Next;
		free(s);
		DeleteElement(L, Value);
	} else {
		DeleteElement(&((*L)->Next), Value);

	}
}
void PrintList(SqList L) {
	SqList s;
	s = L;
	while (s != NULL) {
		printf("%d\t", s->data);
		s = s->Next;
	}
	printf("\n");
}
int main() {
	SqList L = NULL;
	int num;
	L = CreateList(L);
	printf("您创建的链表：\n");
	PrintList(L);
	printf("请输入您想删除的节点的值\n");
	scanf("%d",&num);
	DeleteElement(&L, num);
	PrintList(L);
	return 0; 
}

2.在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一，试编写算法以实现上述操作。

/*设计一个递归算法，删除带头结点的单链表L中所有值为x的结点*/
#include <stdio.h>
#include <stdlib.h>
typedef struct Link {
	int data;//代表数据域
	struct Link* next;// 代表指针域，指向直接后继元素
} link; //link为节点名，每个结点都是一个link结构体
link* initLink() {
	link * p = (link*)malloc(sizeof(link)); //创建一个头结点
	link * temp = p; //声明一个指针指向头结点，
	//头结点的数据域内没有东西 指针域内指向第一个数据域内有东西的结点
	//生成链表
	for (int i = 1; i <= 10; i++) {
		link* a = (link*)malloc(sizeof(link)); //每一个for循环创建一个结点
		a->data = i;
		a->next = NULL; //结点的指针域为空
		temp->next = a; //temp结点的next为新创建的结点
		temp = temp->next; //完成上一步后让最新的结点就是temp结点
	}
	return p;
}
void display(link* p) {
	link* temp = p; //将temp指针重新指向头结点
	//只要temp指针指向的结点的Next不是NULL,就执行输出语句
	while (temp->next) {
		printf("%d ", temp->data);
		temp = temp->next;
	}
	printf("\n");
}
void Del_X_recursion(link* L, link* h, int X) {
	if (h == NULL) return; // 递归函数出口return；
	if (h->data != X) { // 若L所指结点的值不为X
		Del_X_recursion(L->next, h->next, X); // 递归调用
		return; //递归出口return；
	}
	if (h->data == X) {
		link* p;
		p = h; // p指向要删除的结点
		h = h->next;
		L->next = h;
		p->data = 0;
		free(p);
		Del_X_recursion(L, h, X); // 递归调用
	}
}
int main() {
	//初始化链表
	printf("初始化链表为：\n");
	link* p = initLink();
	p = p->next;
	link* h = p->next;
	display(p);
	/*设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点*/
	Del_X_recursion(p, h, 5);
	display(p);
}

3.设L为带头结点的单链表,编写算法实现从尾到头反向输出

#include <stdio.h>
#include <stdlib.h>
typedef struct Link {
	int data;//代表数据域
	struct Link* next;// 代表指针域，指向直接后继元素
} link; //link为节点名，每个结点都是一个link结构体
link* initLink() {
	link * p = (link*)malloc(sizeof(link)); //创建一个头结点
	link * temp = p; //声明一个指针指向头结点，
	//头结点的数据域内没有东西 指针域内指向第一个数据域内有东西的结点
	//生成链表
	for (int i = 1; i <= 10; i++) {
		link* a = (link*)malloc(sizeof(link)); //每一个for循环创建一个结点
		a->data = i;
		a->next = NULL; //结点的指针域为空
		temp->next = a; //temp结点的next为新创建的结点
		temp = temp->next; //完成上一步后让最新的结点就是temp结点
	}
	return p;
}
link *reverse(link*head) { //反转结点
	link*p = head->next;
	link*q = p;

	head->next = NULL;
	while (p) {
		q = q->next;
		p->next = NULL;
		p->next = head->next;
		head->next = p;
		p = q;
	}
	return head;
}
void Print(link*head) { //打印所有节点
	link*p = head->next;
	while (p){
	printf("%4d", p->data);
	p = p->next;
	}
	printf("\n");
}
int main(){
	//初始化链表
	link* p = initLink();
	Print(p);
	reverse(p);
	Print(p);
	return 0;
}

4.试编写在带头结点的单链表L中删除一个最小值结点的高效算法（假设最小值结点是唯一的）。

#include <stdio.h>
#include <stdlib.h>
typedef struct Link {
	int data;//代表数据域
	struct Link* next;// 代表指针域，指向直接后继元素
} link; //link为节点名，每个结点都是一个link结构体
link* initLink() {
	link * p = (link*)malloc(sizeof(link)); //创建一个头结点
	link * temp = p; //声明一个指针指向头结点，
	//头结点的数据域内没有东西 指针域内指向第一个数据域内有东西的结点
	//生成链表
	for (int i = 2; i <= 10; i++) {
		link* a = (link*)malloc(sizeof(link)); //每一个for循环创建一个结点
		a->data = i;
		a->next = NULL; //结点的指针域为空
		temp->next = a; //temp结点的next为新创建的结点
		temp = temp->next; //完成上一步后让最新的结点就是temp结点
	}
	return p;
}
link *Delete (link *L){
	link *p=L->next;
	link *pre=L; // pre指向头结点
	link *q=p; // 假设第一个结点为最小值的结点
	while (p->next != NULL){
		if(p->next->data < q->data){
			pre=p;
			q=p->next;
		}
		p=p->next;
	}
	pre->next=q->next; // 从链表上删除最小值结点
	free (q);
}
void Print(link*head) { //打印所有节点
	link*p = head->next;
	while (p){
		printf("%4d", p->data);
		p = p->next;
	}
	printf("\n");
}
int main() {
	link* p = initLink();
	Print(p);
	Delete(p);
	Print(p);
	return 0;
}

5.试编写算法将带头结点的单链表就地逆置,所谓“就地”是指辅助空间复杂度为O(1)

解法一：将头结点摘下，然后从第一结点开始，依次前插入到头结点的后面（头插法），直到最后一个结点为止。

完整代码：

#include <stdio.h>
#include <stdlib.h>
typedef struct Link {
	int data;//代表数据域
	struct Link* next;// 代表指针域，指向直接后继元素
} link; //link为节点名，每个结点都是一个link结构体
link* initLink() {
	link * p = (link*)malloc(sizeof(link)); //创建一个头结点
	link * temp = p; //声明一个指针指向头结点，
	//头结点的数据域内没有东西 指针域内指向第一个数据域内有东西的结点
	//生成链表
	for (int i = 2; i <= 10; i++) {
		link* a = (link*)malloc(sizeof(link)); //每一个for循环创建一个结点
		a->data = i;
		a->next = NULL; //结点的指针域为空
		temp->next = a; //temp结点的next为新创建的结点
		temp = temp->next; //完成上一步后让最新的结点就是temp结点
	}
	return p;
}
link *reverse (link *L){
	link *p=L->next;
	L->next = NULL;
	while(p != NULL){
		link *r = p->next;
		p->next = L->next;
		L->next = p;
		p =r;
	}
	return L;
}
void Print(link*head) { //打印所有节点
	link*p = head->next;
	while (p){
		printf("%4d", p->data);
		p = p->next;
	}
	printf("\n");
}
int main() {
	link* p = initLink();
	Print(p);
	reverse(p);
	Print(p);
	return 0;
}

解法二：通过若干操作将指针反转达到逆置的目的。

假设pre、p和r指向3个相邻的结点，如上图。pre之前的结点的指针都已经调整完毕，它们的next指针都指向其原前驱结点。现在令p结点的next域指向pre结点，注意到一旦调整指针的指向后，p的后继结点的链就断开了，为此用r来指向原*p结点的后继结点。

处理第一个结点时，将其next域置为NULL,。处理最后一个结点后，将头结点的指针指向它。

完整代码：

#include <stdio.h>
#include <stdlib.h>
typedef struct Link {
	int data;//代表数据域
	struct Link* next;// 代表指针域，指向直接后继元素
} link; //link为节点名，每个结点都是一个link结构体
link* initLink() {
	link * p = (link*)malloc(sizeof(link)); //创建一个头结点
	link * temp = p; //声明一个指针指向头结点，
	//头结点的数据域内没有东西 指针域内指向第一个数据域内有东西的结点
	//生成链表
	for (int i = 2; i <= 10; i++) {
		link* a = (link*)malloc(sizeof(link)); //每一个for循环创建一个结点
		a->data = i;
		a->next = NULL; //结点的指针域为空
		temp->next = a; //temp结点的next为新创建的结点
		temp = temp->next; //完成上一步后让最新的结点就是temp结点
	}
	return p;
}
link *reverse (link *L) {
	link *pre, *p = L->next, *r = p->next;
	p->next = NULL; //处理第一个结点
	while(r!=NULL){
		pre = p;
		p = r;
		r = r->next;
		p->next = pre;
	}
	L->next = p;
	return L;
}
void Print(link*head) { //打印所有节点
	link*p = head->next;
	while (p) {
		printf("%4d", p->data);
		p = p->next;
	}
	printf("\n");
}
int main() {
	link* p = initLink();
	Print(p);
	reverse(p);
	Print(p);
	return 0;
}

6.有一个带头结点的单链表L,设计一个算法使其元素递增有序。

void sort(link *L){
	link *p, *pre;
	link *s;
	p = L->next;
	s = p->next;     //s指向要进行操作的链表
	p->next = NULL; // 构成一个只含一个数据结点的有序表，初始时只有一个元素
	while (s!=NULL)
	{
		p = s;   //p指向当前链表要进行操作的元素
		s = s->next;  //s继续指向链表的下一个结点   
		pre = L;
		while (pre->next != NULL && pre->next->data <p->data)
		{
			pre = pre->next;      //在有序表中找到插入位置
		}
		p->next = pre->next;//在有序表的相应位置插入
		pre->next = p;		
	}
}

7．设在一个带表头结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有介于给定的两个值（作为函数参数给出）之间的元素的元素（若存在）。

链表无序，逐个结点进行检查，执行删除

void rangeDelete(link* L, int min, int max) {
	link* pr = L, * p = L->next;
	while (p != NULL) {
		if (p->data > min && p->data < max) {
			pr->next = p->next;
			free(p);
			p = pr->next;
		} else {
			pr = p;
			p = p->next;
		}
	}
}

8．给定两个单链表，编写算法找出两个链表的公共结点。

两个链表有公共节点，即两个结点从某个节点开始，他们的next结点都指向同一个结点；由于单链表的结点只能指向一个结点，所以后面都是重合的，不会出现分叉。拓扑形状为Y。

应注意到这样一个事实:若两个链表有一个公共结点, 则该公共结点之后的所有结点都是重合的,即它们的最后一个结点依然是重合的。因此, 我们判断两个链表是不是有重合的部分时, 只需要分别遍历两个链表到最后一个结点。若两个尾结点是一样的, 则说明它们有公共结点, 否则两个链表没有公共结点。然而, 在上面的思路中, 顺序遍历两个链表到尾结点时, 并不能保证在两个链表上同时到达尾结点。这是因为两个链表长度不一定一样。但假设一个链表比另一个长k个结点, 我们先在长1的链表上遍历k个结点, 之后再同步遍历, 此时我们就能保证同时到达最后一个结点。由于两个链表从第一个公共结点开始到链表的尾结点, 这一部分是重合的, 因此它们肯定也是同时到达最后一个公共结点的。于是在遍第一个相同的结点就是第一个公共的结点。根据这一思路中, 我们先要分别遍历两个链表得到它们的长度, 并求出两个长度之差。在长的链表上先遍历长度之差个结点之后, 再同步遍历两个链表, 直到找到相同的结点, 或者, 直到链表结束。

link* Search_lst_Common(link *L1, link *L2) {
	int dist = 0;
	int len1 = getListLength(L1), len2 = getListLength(L2);
	link *longList, *shortList;
	if (len1 > len2) {
		longList = L1->next; shortList = L2->next;
		dist = len1 - len2;
	}
	else {
		longList = L2->next; shortList = L1->next;
		dist = len2 - len1;
	}
	
	while (dist--)
		longList = longList->next;
	while (longList != NULL)
	{
		if (longList == shortList)
			return longList;
		else {
			longList = longList->next;
			shortList = shortList->next;
		}
	}
	return NULL;
}

9．给定一个带表头结点的单链表，设head为头指针，结点结构为（data，next），data为整型元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作为辅助空间）。

算法思想：链表遍历，每次遍历中找出整个链表的最小值元素，输出并释放结点所占空间；再查找次小值元素，输出并释放空间，如此下去，直至链表为空。

void minDelete(link *head) {
	link* pre,* u,*p;
	while (head->next != NULL) {
		pre = head;
		p = pre->next;
		while (p->next != NULL) {
			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(head);
}

10．将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。

算法思想：遍历完整表，分别计算奇偶元素，分别尾插入到A和B表

link *disCreat(link* A) {
	link* B,*p;
	int i = 0;
	B = (link*)malloc(sizeof(link));
	B->next = NULL;
	link *ra = A, *rb = B;
	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;
}

11．设C＝｛a1，b1，a2，b2，··，an，bn｝为线性表，采用带头结点的单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A＝｛a1，a2，···，an｝，B＝｛bn，··，b2，b1｝。

（题目变形：将一个带结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中的序号为偶数的元素，B表为逆序。）

link *disCreat(link *A) {
	link *B = (link*)malloc(sizeof(link));
	B->next = NULL;
	link* p = A->next, * q;
	link* 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;
}

12.在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素，例如（7，10，10，21，30，42，42，42，51，70）将变为（7，10，21，30，42，51，70）。

void delSame(link* L) {
	link* 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;
	}
}

13.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

void mergeList(LinkList* L1,LinkList* L2){
    //将L2插入到L1中
    LinkList* p = L1->next;;
    LinkList* p2 = L2->next;;
    L1->next = NULL;
    //头插法
    while(p!=NULL && p2!=NULL){
        if(p->data>p2->data){
            //p2头插
            LinkList* p2_next = p2->next;//防短链
            p2->next = L1->next;
            L1->next = p2;
            p2 = p2_next;
        }else
        {
            //p头插
            LinkList* p_next = p->next;
            p->next = L1->next;
            L1->next = p;
            p = p_next;
        }
    }
    while(p2!=NULL){
            LinkList* p2_next = p2->next;//防短链
            p2->next = L1->next;
            L1->next = p2;
            p2 = p2_next;
    }
    while(p!=NULL){
            LinkList* p_next = p->next;
            p->next = L1->next;
            L1->next = p;
            p = p_next;
    }
}

14.设A和B是两个单链表（带头结点），其中元素递增有序。设计一个算法从A和B中的公共元素产生单链表C，要求不破坏A、B的结点。

void Get_Common(LinkList A, LinkList B) {
    LNode* p = A->next, * q = B->next, * r, * s;
    LinkList C = (LinkList)malloc(sizeof(LNode));
    r = C;
    while (p != NULL && q != NULL) {
        if (p->data < q->data)
            p = p->next;
        else(p->data > q->data)
            q = q->next;
        else {
            s = (LNode*)malloc(sizeof(LNode));
            s->data = p->data;
            r->next = s;
            r = s;
            p = p->next;
            q = q->next;
        }
    }
    r->next = NULL;
}

15.已知两个链表A和B分别表示两个集合，其元素递增排列。编制函数，求A与B的交集，并存放于A链表中。

void getCommon(link* L1,link* L2){
	link *p,*q,*r,*s;
	p = L1->next;
	q = L2->next;
	L1->next = NULL;
	s = L1;
	while(p != NULL && q != NULL){
		if(p->data < q->data){
			r = p->next;
			free(p);
			p = r;
		}else if(p->data>q->data){
			r = q->next;
			free(q);
			q = r;
		}else{
			s->next = p;
			p = p->next;
			r = q->next;
			free(q);
			q = r;
			s = s->next;	
		}
	}
	s->next = NULL;
	while(q != NULL){
		r = q->next;
		free(q);
		q = r;
	}
	while(p!=NULL){
		r = p->next;
		free(p);
		p = r;
	}
	free(L2);
}

16.两个整数序列A＝a1，a2，a3，...an和B＝b1，b2，b3，···，bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的连续子序列。

算法思想: 因为两个整数序列已存入两个链表中,操作从两个链表的第一个结点开始,若对应数据相等,则后移指针;若对应数据不等,则A链表从上次开始比较结点的后继开始,B链表仍从第一个结点开始比较,直到B链表到B尾表示匹配成功.A链表到尾,而B链没到尾表示失败.操作中应记住A链表每次的开始结点,以便下次匹配时好从其后继开始.

void Pattern(link *A,link *B) {
	//A和B分别是数据域为整数的单链表,本算法判断B是否是A的子序列
	link *p = A->next,*pre = p, *q = B->next;
	//p,q为工作指针,pre记住每趟比较中A链表的开始结点
	while(p&&q) {
		if(p->data==q->data) { //结点值相同
			p=p->next;
			q=q->next;
		} else {
			pre=pre->next;
			p=pre;//A链表从新的开始比较结点
			q=B->next;//q从B链表第一个结点开始
		}
	}
	if(q==NULL) //B到表尾
		printf("\n序列B是序列A的连续子序列") ;
	else//A到表尾
		printf("\n序列B不是序列A的连续子序列") ;
	
}

17．设计一个算法用于判断带头结点的循环双链表是否对称。

int Symmtry(DLinkList L) {
    DNode* p = L->next, * q = L->prior;
    while (p != q && q->next != p) {  //考虑链表的奇偶
        if (p->data == q->data) {
            p = p->next;
            q = q->prior;
        }
        else
            return 0;
    }
    return 1;
}

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

算法思想：找到尾指针即可

LinkList Link(LinkList *h1, LinkList *h2) {
    LNode* p, * q;
    p = h1;
    while (p->next != h1) {
        p = p->next;
    }
    q = h2;
    while (q->next != h2) {
        q = q->next;
    }
    p->next = h2;
    q->next = h1;
    return h1;
}

19．设有一个带头结点的循环单链表，其结点值均为正整数。设计一个算法，反复找出单链表中结点值最小的结点并输出，然后将该结点从中删除，直到单链表空为止，再删除表头结点。

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

20．设头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pre（前驱指针）、data（数据）和next（后继指针）域外，还有一个访问频度域freq。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate（L，x）运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点前面，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate（L，x）运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。

DLinkList Locate(DLinkList& L, ElemType x) {
    DNode* p = L->next, * q;
    while (p && p->data != x)
        p = p->next;
    if (!p) {
        printf('不存在结点为x');
        exit(0);
    }
    else {
        p->freq++;
        //断链
        if (p->next != NULL) {
            p->next->pre = p;
            p->pre->next = p->next;
        }
        q = p->pre;
        while (q != L && q->fre <= p->fre) {
            q = q->pre;
        }
        q->next->pre = p;
        p->next = q->next;
        q->next = p;
        p->pre = q;
    }
    return p;
}

21．单链表有环，是指单链表的最后一个结点的指针指向了链表中的某个结点（通常单链表的最后一个结点的指针域是空的）。试编写算法判断单链表是否存在环。

1）给出算法的基本设计思想。

2）根据设计思想，采用C或C＋＋语言描述算法，关键之处给出注释。

3）说明你所设计算法的时间复杂度和空间复杂度。

思路分析：单链表有环，是指单链表中某个节点的next指针域指向的是链表中在它之前的某一个节点，这样在链表的尾部形成一个环形结构。

// 链表的节点结构如下
typedef struct node
{
    int data;
    struct node *next;
} NODE;

算法思想：

定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就是环形链表；如果走得快的指针走到了链表的末尾（next指向 NULL）都没有追上第一个指针，那么链表就不是环形链表。

// 判断链表是否有环
bool IsLoop(NODE *head) // 假设为带头节点的单链表
{
    if (head == NULL)
        return false;

    NODE *slow = head->next; // 初始时，慢指针从头节点开始走1步
    if (slow == NULL)
        return false;

    NODE *fast = slow->next; // 初始时，快指针从头节点开始走2步
    while (fast != NULL && slow != NULL) // 当单链表没有环时，循环到链表尾结束
    {
        if (fast == slow)
            return true;

        slow = slow->next; // 慢指针每次走一步

        fast = fast->next;
        if (fast != NULL)
            fast = fast->next;
    }

    return false;
}

22．【2009统考真题】已知一个带有表头结点的单链表，结点结构为

假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：

1）描述算法的基本设计思想。

2）描述算法的详细实现步骤。

3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C、C＋＋或Java 语言实现），关键之处请给出简要注释。

注意：这里的链表中没有给出链表长度

思路：设置两个指针p、q，分别指向该链表的第一个元素（头结点的下一个元素）和头结点，一个整数num（初值为1）， p向后移动一个位置num值加1，如果num值大于k，则p，q一起移动，p移动到表尾，q指针指的就是倒数第k个位置上的结点。如果链表结束，q一直是指向头结点，那么该结点不存在。

Status findElem(LinkList L, int k)
{
    LinkList q, p;
    p = L->next;    //指向第一个
    q = L;
    int num = 1;

    while (p!=NULL)
    {
        p = p->next;
        num++;
        if (num > k)
            q = q->next;
    }
    if (q == L)
        return ERROR;
    printf("%d", q->data);
    return OK;
}

23．【2012统考真题】假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间，例如，loading和being的存储映像如下图所示。

设 strl 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为

请设计一个时间上尽可能高效的算法，找出由 strl 和 str2 所指向两个链表共同后缀的起始位置（如图中字符i所在结点的位置p），要求：

1）给出算法的基本设计思想。

2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

3）说明你所设计算法的时间复杂度。

顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长 k 个结点，我们先在长链表上遍历 k 个结点，之后同步遍历两个链表，这样就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的，所以它们肯定同时到达第一个公共结点。

算法的基本设计思想：

① 分别求出 str1 和 str2 所指的两个链表的长度 m 和 n 。

② 将两个链表以表尾对齐：令指针 p 、 q 分别指向 str1 和 str2 的头结点，若 m>=n ，则使 p 指向链表中的第 m-n+1 个结点；若 m<n ，则使 q 指向链表中的第 n-m+1 个结点，即使指针 p 和 q 所指的结点到表尾的长度相等。

③ 反复将指针 p 和 q 同步向后移动，并判断它们是否指向同一结点。若 p 和 q 指向同一结点，则该点即为所求的共同后缀的起始位置。

时间复杂度为： O(len1+len2) 或 O(max(len1,len2)) ，其中 len1 、 len2 分别为两个链表的长度。

int getListLength(LinkList*list)//求链表长度
{
    int n=0;
    LinkList*p=list;
    while(p->next!=NULL)
    {
    n++;
    p=p->next;
    }
    return n;
}
LinkNode *Find_1st_Common(LinkList str1,LinkList str2){
    int len1=getListLength(str1),len2=getListLength(str2);
    LinkNode *p,*q;
    for(p=str1;len1>len2;len1--)             // 使 p 指向的链表与 q 指向的链表等长
    	p=p->next;
    for(q=str2;len1<len2;len2--)             // 使 q 指向的链表与 p 指向的链表等长
    	q=q->next;
    while(p->next!=NULL&&p->next!=q->next){ // 查找共同后缀起始点
        p=p->next;                          // 两个指针同步向后移动
        q=q->next;
    }
    return p->next;                             // 返回共同后缀的起始点
}

24．【2015统考真题】用单链表保存m个整数，结点的结构为［data］［link］，且｜data｜≤n（n为正整数）。现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表head 如下：

要求：

1）给出算法的基本设计思想。

2）使用C或C＋＋语言，给出单链表结点的数据类型定义。

3）根据设计思想，采用C或C＋＋语言描述算法，关键之处给出注释。

4）说明你所设计算法的时间复杂度和空间复杂度。

基本设计思想：

用空间换时间，使用辅助数组记录链表中已出现的数值，从而只需要对链表进行一趟扫描；
因为｜data｜<=n，所以辅助数组q的大小为n+1，各元素的初始值均为0。
依次扫描链表中各结点，同时检查q[addr]（addr=｜data｜）的值；如果q[addr]的值为0，则保留该结点，并令q[addr]的值为1；否则将该结点从链表中删除；

时间复杂度：O(m); 空间复杂度：O(n);

void simplify_list(LinkList *head,int n){
    //申请n+1个位置的辅助数组；
    q = (int *)malloc(sizeof(int)*(n+1));
    for(int i=0;i<n+1;i++){//数组元素初值设为0；
        q[i] = 0;
    }
    LNode *p = head->next;
    pre = head;
    while(p !=NULL){
        int data = p->data;
        int addr = data >0 ? data:-data;        
        if(q[addr] ==1){//需要删除当前节点p
            temp = p;
            pre->next = p->next;
            p=p->next;
            free(temp);
        }else{//保留当前节点;
            q[addr] =1;
            pre = p;
            p = p->next;
        }  
    }
	free(q);  //释放辅助空间；
}

【2019统考真题】设线性表L=（a1，，a2，a3，，，an-2，an-1，an）采用带头结点的单链表保存，链表中的结点定义如下：

typedef struct node{
    int data;
    struct node*next;
}NODE;

请设计一个空间复杂度为O（1）且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L＇＝（a1，an，a2，an-1，a3，an-2，···）。要求：

1）给出算法的基本设计思想。

2）根据设计思想，采用C或C＋＋语言描述算法，关键之处给出注释。

3）说明你所设计的算法的时间复杂度。

void change(NODE *head)
{
    if(head==null||head->next==null||head->next->next==null)return head;
    NODE *slow=head,*fast=head;
    while(fast->next!=null)
    {
        slow=slow->next;
       fast=fast->next;
        if(fast->next!=null)fast=fast->next;
    }
    NODE *pre=slow->next,*curr=pre->next;
    pre->next=null;
    while(curr->next!=null)
    {
         NODE *nex=curr->next;
         curr->next=slow->next;
          slow->next=curr;
          curr=nex;
    }
    curr->next=slow->next;
    slow->next=curr;
    NODE *B=slow->next,*A=head->next,*b=B->next,*a=A->next;
    slow->next=null;
    NODE *new_head=head,*p=head;
    while(A!=null||B!=null)
    {
        p->next=A;
        A=a;
        a=a->next;
        p=p->next;
        p->next=B;
        B=b;
        b=b->next;
        p=p->next;
    }
    return new_head;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-09-05，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构