前言

这个系列我本来是想在刷力扣热题100的时候做的系列,就是记录一些好的算法题和思路,没想到数据结构课上的作业题留的还真挺有意思,难度也够用,也需要一定的代码能力,数据结构本身对于算法来说还是很重要的. 所以我直接就拿我们本次的数据结构作业作为第一次刷题，其实上一次作业也挺好的,里面也有两道不错的题目.

上一次的两道题

1、 对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。
2、定义三元组(a, b, c)（a、b、c均为正数）的距离D = |a - b| + |b - c| + |c - a|。给定3个非空整数集合S1、S2和S3，按升序分别存储在3个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a, b, c)（a ∈ S1, b ∈ S2, c ∈ S3)中的最小距离。例如 S1 = { -1, 0, 9}，S2 = {-25, -10, 10, 11}, S3 = {2, 9, 17, 30, 41}，则最小距离为2，相应的三元组为（9，10，9）。要求：
（1）给出算法的基本设计思想
（2）根据设计思想，采用C语言或C++语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。

答案链接： 个人博客

本次三道题

一、

1.设线性表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, …)。要求：
a. 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
b. 说明你所设计的算法的时间复杂度。
解答：思路也在里面

//思路：1. 找到中间的节点,快慢指针法(很常用,需要记住),慢指针和快指针一起走,快指针一次走两步
//         慢指针一次走一步,当快指针的next为空或者next的next为空的时候 slow走到了中间节点
//     2. 逆置中间节点以后的链表,注意:改指向即可,不需要多余空间
//     3.前半部分和后半部分交替排列,得到结果 

//  比如1->2->3->4->5    第一步：找到中间节点3 第二步: 逆置 1->2->5->4->3
//                       第三步:交替 1->5->2->4->3
 
 // 时间复杂度O(N) --遍历了几次链表 
 //空间复杂度O(1) --- 不需要额外空间 
 //   
#include<bits/stdc++.h>
using namespace std;
class Node{
public:
	int data;
	Node* next;
	Node(int x)
	   :data(x),next(NULL)
	{}
	
}; 
Node* MiddleNode(Node* head)
{
	head = head->next;//头节点 
	Node* slow = head->next,*fast = slow;
	while(fast -> next != nullptr && fast -> next -> next != nullptr)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	return slow;
}
Node* Reverse_MiddleAfter_Node(Node* head)
{
	Node* prev = nullptr,*cur = head;
	while(cur)
	{
	  Node* next = cur->next;
	  cur->next = prev;
	  prev = cur;
	  cur = next;	
	}
	return prev; //返回新头节点 
}
void MergeList(Node*head)
{
	Node* phead = head->next;
	Node* middle = MiddleNode(head);
	Node* head2 = middle->next;
	middle->next = nullptr;
	head2 = Reverse_MiddleAfter_Node(head2);
	//合并
	Node* p = phead,*q = head2;
	while(q)
	{
	   Node* pnext = p->next;
	   Node* qnext = q->next;
	   p->next = q;
	   q->next = pnext;
	   p = pnext;
	   q = qnext;	
    }
}
int main()
{
    return 0;
}

二、

2.假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间，例如，“loading”和“being”,如下图所示
在这里插入图片描述
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为：
在这里插入图片描述
请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置(如图中字符i所在结点的位置p)。要求：
a.根据设计思想，采用C、C++语言描述算法，关键之处给出注释。
b.说明你所设计算法的时间复杂度。

这题本质就是求链表相交的节点, 可以用set但不是最优雅的解，正解:

//思路:求出两个链表的长度,让长的链表先走差距的步数,
//然后再一起走,相等就是相交节点. 
//时间复杂度O(n),空间复杂度O(1)  不需要额外空间 
#include<bits/stdc++.h>
using namespace std;
class Node{
public:
  char c;
   Node* next;
   Node(char a)
     :c(a),next(nullptr)
	 {}	
};
Node* FindSameAfter(Node* head1,Node*head2)
{
	Node*phead1 = head1->next,*phead2 = head2->next;
	
	Node* cur1 = phead1,*cur2 = phead2,*tail1 = cur1,*tail2 = cur2;
	int lenA = 0,lenB = 0; 
	while(cur1)
	{
		cur1 = cur1->next;
		tail1 = cur1;
		lenA++;
	}
	while(cur2)
	{
		cur2 = cur2->next;
		tail2 = cur2;
		lenB++; 
	}
	if(tail1 != tail2)
	{
		return nullptr;
	}
	int gap = abs(lenA - lenB);
	//默认A长
	if(lenA < lenB) swap(phead1,phead2);
	
	while(gap--) phead1 = phead1->next;
	while(phead1 != phead2)
	{
		phead1 = phead1->next;
		phead2 = phead2->next;
	}
	return phead1; 
}
int main()
{
	return 0;
}

三、

约瑟夫环问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀的顺序是：5，4，6，2，3，1。
【输入形式】输入两个正整数N和M，N表示N个人，M表示报数到M；
【输出形式】输出依次出列的序号。以空格作为分隔。
【样例输入1】
6 5
1 2 3 4 5 6
【样例输出1】
5 4 6 2 3 1
这题相对简单一点,一个双向循环链表即可实现,带不带头都无所谓
思路：

//双向链表简单模拟一下即可 

#include<bits/stdc++.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
using namespace std;
typedef struct DlistNode
{
	struct DlistNode* next;
	struct DlistNode* prev;
	int data;
}LTNode;
LTNode *BuyListnode(int x)
{
	LTNode* node =(LTNode*) malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc");
		return NULL;
	}
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}
LTNode* LTInit()
{
	LTNode * head = BuyListnode(-1);
	head->next = head;
	head->prev = head;
	return head;
}
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("<=head=>");
	while (cur != phead)
	{
		printf("%d <=>", cur->data);
		cur = cur->next;
	}
}

void Destory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}
void LTPushback(LTNode* phead, int x)
{
	assert(phead);
	LTNode* newnode = BuyListnode(x);
	LTNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next =phead;
	phead->prev = newnode;
}
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
void LTPopback(LTNode* phead, int x)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	tailprev->next = phead;
	phead->prev = tailprev;
	free(tail);
	tail = NULL;
}
void LTPushfront(LTNode* phead, int x)
{
	assert(phead);
	LTNode* node = BuyListnode(x);
	node->next = phead->next;
	phead->next->prev = node;
	phead->next = node;
	node->prev = phead;
}
void LTPopfront(LTNode* phead)
{

	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* next = phead->next;
	phead->next = next->next;
	next->next->prev = phead;
}
LTNode* LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL; 
	return next;
}
void LTInsert(LTNode* pos, int x)
{
	LTNode* newnode = BuyListnode(x);
	LTNode * next = pos->next;
	pos->next = newnode;
	newnode->prev = pos;
	newnode->next = next;
	next->prev = newnode;
}
LTNode* find(LTNode* phead, int x)
{

	LTNode *find = phead->next;
	while (find != phead)
	{
		if (find->data == x)
		{
			return find;
		}
		find = find->next;
	}
	return NULL;
}


int main()
{
	int n,m;cin >> n >> m;
   LTNode* head = LTInit();
	
	for(int i = 0;i < n;++i)
	{
		int x; cin >> x;
	  	LTPushback(head,x);
	}
	LTNode* cur = head->next;
	int time = 0,cnt = 1;
	while(time != n)
	{
		if(cnt == m)
		{
			cout << cur->data << ' ';
			cur = LTErase(cur);
			if(cur == head)
			{
			cur = cur -> next;
		    }
			cnt = 1;
			time++;
		}
		cnt++;
		cur = cur->next;
		if(cur == head)
		{
			cur = cur -> next;
		}
	}
	return 0;
}

总结:

目前主要还是更新数据结构,等Linux学差不多和对应书籍看完就更新Linux，刷题不定时更.

# c++ # 链表
Logo
AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

cover

程序员学 AI（八）：AI Agent 到底是什么？从回答问题到完成任务

avatar AI Agent技术社区
cover

22道AI Agent 工程师必会的面试题，别啥都不会就出去找工作

avatar AI Agent技术社区
cover

基于AI agent的智能图书馆

avatar AI Agent技术社区