蓝桥杯备赛：顺序表和单链表相关算法题详解（上）

目录

一.询问学号（顺序表）

1.题目来源：

2.解析与代码实现：

（1）解析：

（2）代码实现：

二.寄包柜（顺序表）

1.题目来源：

2.解析与代码实现：

（1）解析：

（2）具体代码：

三.快慢指针（单链表）

1.反转链表：

主要思路：三指针法

2.回文结构：

主要思路：快慢指针和三指针反转

四.交叉链表

1.题目：

2.解析与代码实现：

一.询问学号（顺序表）

1.题目来源：

https://www.luogu.com.cn/problem/P3156

（洛谷原题）

2.解析与代码实现：

（1）解析：

首先结合题目和输出样例不难看出这道题目是围绕两个变量：学生个数n和询问次数m，分别代表着第二行和第三行输入数据的个数，因此n和m就非常容易地可以作为接下来我们实现代码里的范围参数，因为当我们在一串数字（这里也就是顺序表）里查找某一个给定的数字就免不了要去遍历这传数字（顺序表）因此就需要这串数字的数字个数来作为遍历循环的范围条件乃至于通过对其减少以便将其作为判断循环是否结束的条件，所以这题的代码思路就很容易可以得到了：首先确定需要我们输入的变量有三行：第一行的n和m，第二行的n个数字，第三行的m个数字，因此就会产生两个循环，然后就是在这两个循环里分别实现数组的输入和指定数组成员的输出就行了

（2）代码实现：

#include<iostream>
#include<vector>

using namespace std;

const int N = 2e6 ;//定义一下学生的最大个数

int n, m;//定义全局变量m，n
vector<int>a(N);//创建一个变长数组a

int main()
{
	//初始化数组（即使用户输入题目里第二行的数组成员）
	cin >> n >> m;
	for (int q = 0; q < n; q++)
	{
		cin >> a[q];
	}

	//根据用户输入的序号（第三行）查找上面的数组的特定元素
	while (m--)
	{
		int p;
		cin >> p;
		cout << a[p] << endl;
	}
	
	return 0;
}

二.寄包柜（顺序表）

1.题目来源：

https://www.luogu.com.cn/problem/P3613

（洛谷原题）

2.解析与代码实现：

（1）解析：

这题粗略浏览下来会感觉有些麻烦，但多读几遍其实也不是非常难以理解，简单来说，这题有以下几个参数：寄包柜个数n，询问次数q，第i个柜子，第j个格子以及存入操作（1），查看操作（2），代码大概实现思路就是通过变长数组（vector）进行存入操作，然后再对用户的输入来判断查找还是存入，最后通过数组访问读取即可，并且存入时再多关注一下空间是否充裕，不够的话用resize扩容即可

（2）具体代码：

#include<iostream>
#include<vector>
using namespace std;

const int N = 1e5 + 10;//单纯为了防止空间不够而多加了10个空间

vector<int>abc[N];//创建N个柜子

int n, q;//创建全局变量
int main()
{
	cin >> n >> q;
	while(q--)
	{
		int option, i, j, k;
		cin >> option >> i >> j;
		//存入
		if (option == 1)
		{
			cin >> k;
			//判断空间是否充足
			if (abc[i].size() <= j)
			{
				//扩容
				abc[i].resize(j + 1);
			}
			abc[i][j] = k;
		}
		else
		{
			//查询
			cout << abc[i][j] << endl;
		}

	}
	return 0;
}

代码这里有一点值得关注一下就是为啥一定要使用vector变长数组而不使用一般的二维数组，如果我使用普通的二维数组：abc[N][N]，那这里就相当于要开辟N*2个柜子，而这是与题目要求范围相悖的

三.快慢指针（单链表）

1.反转链表：

原题链接：https://leetcode.cn/problems/reverse-linked-list/description/

主要思路：三指针法

通过三个指针的循环往后移动并在移动过程中改变每一个结点指向从而实现在遍历链表后实现所有结点之间指针方向的改变，同时需要注意的就是在循环的最后，n2和n3指针都指向NULL

#include<stdio.h>

struct ListNode 
{
	int val;
	struct ListNode* next;
};

typedef struct ListNode ListNode;

struct ListNode* reverseList(struct ListNode* head) 
{
	if (head == NULL)
	{
		return head;
	}
	ListNode* n1, *n2, *n3;
	n1 = NULL, n2 = head, n3 = n2->next;
	while (n2)
	{
		n2->next = n1;//改变链表结点之间的指针指向
		n1 = n2;
		n2 = n3;
		if (n3)
		{
			n3 = n3->next;
		}
	}
	//跳出循环说明此时n2(n3也是)为空
	return n1;
}

2.回文结构：

原题链接：https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa

主要思路：快慢指针和三指针反转

具体思路主要就是先通过快慢指针找到回文结构的中间位置，然后反转链表并将其与原链表进行遍历比较，如果一样就是回文结构，但这道题其实还有个小漏洞，就是因为题目在限制范围后我们其实就可以讲链表里的数据遍历载入一个数组中然后分别再从头尾进行遍历比较，这是一种钻空子的做法，但就此题来说也不是不行

#include<stdio.h>

struct ListNode 
{
	int val;
	struct ListNode* next;
};

typedef struct ListNode ListNode;

//找中间结点
ListNode* middleNode(ListNode* head)
{
	//创建快慢指针
	ListNode* fast, * slow;
	head = fast = slow;
	if (fast && fast->next)//注意两者顺序不可以颠倒
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	return slow;
}

//反转链表
ListNode* reverseList(ListNode* head)
{
	if (head == NULL)
	{
		return NULL;
	}
	ListNode* n1, * n2, * n3;
	n1 = NULL, n2 = head, n3 = n2->next;
	n2->next = n1;
	n1 = n2;
	n2 = n3;
	if (n3)
	{
		n3 = n3->next;
	}
	return n1;
}
bool checkpa(ListNode* A)
{
	//1.找中间结点
	ListNode* mid = middleNode(A);
	//2.反转中间结点作为另外一个头的链表
	ListNode* right = reverseList(mid);
	//3.遍历原链表和反转之后的链表，比较结点的值是否相同
	ListNode* left = A;
	//此时反转后的链表指向空，但原链表依旧往后延续，可以参考下图
	while (right)
	{
		if (left->val != right->val)
		{
			return false;
		}
		left = left->next;
		right = right->next;
	}
	return true;
}

四.交叉链表

1.题目：

原题来源：https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

2.解析与代码实现：

这题相比上面的思路就要显得更加简洁，浏览题目易得这题的主要着手点就在于两条链表重合前是否长度相等，因此就可以通过先分别计算出两条链表的长度然后使长链表先走掉比短的那条链表多出来的的长度差，然后再依次遍历比较即可

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    //先求两条链表的长度
    ListNode* pa = headA;
    ListNode* pb = headB;
    int sizeA = 0, sizeB = 0;
    while (pa)
    {
        ++sizeA;
        pa = pa->next;
    }
    while (pb)
    {
        ++sizeB;
        pb = pb->next;
    }
    int gap = abs(sizeA - sizeB);//abs函数求绝对值
    //让长链表先走gap步
    ListNode* longlist = headB;
    ListNode* shortlist = headA;
    if (sizeA < sizeB)
    {
        shortlist = headB;
        longlist = headA;
    }
    while (gap--)
    {
        longlist = longlist->next;
    }
    //此时长短链表处于同一起跑线
    while (shortlist)
    {
        if (shortlist == longlist)
        {
            return longlist;
        }
        shortlist = shortlist->next;
        longlist = longlist->next;
    }
    return NULL;
}

以上就是我在这篇文章里想写的几道题目的全部了

全文终