目录
前言：
大家经过前面的学习，已经对链表有了初步的了解，那么，我为大家准备了几道题目，大家一起来练习巩固一下吧！
一、反转单链表
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。
先来一道简单题来练练手，题目的要求为反转链表，相信会有部分同学会说，像数组一样，从后往前遍历不就行了，对此我只能说，很抱歉，这个是单链表，不是双链表（以后做题无说明均为单链表），那既然是单链表，我们又该如何破局呢？大家可自行思考一下方法。
本题提供的方法为三指针法（方法不唯一，以下题均如此），即运用三指针进行求解。以下为思路：
代码如下：
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
if(head == NULL)
{
return head;
}
ListNode* p1,*p2,*p3;
p1 = NULL,p2 = head,p3 = p2->next;
while(p2)
{
p2->next = p1;
p1 = p2;
p2 = p3;
if(p3)
p3 = p3->next;
}
return p1;
}题目链接：. - 力扣（LeetCode）
大家可自行前去练习。
二、链表的中间结点
给你单链表的头结点
head，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
本题方法为：双指针法。
具体实现思路为：使用快慢指针，一个比另外一个快一步即可。以下是一个例子帮助大家理解：很直观的例子就是五十步笑百步：假设路一共100米，慢逃兵走一步，快逃兵走两步，那么当快逃兵走到终点时，慢逃兵刚好就停在中间，然后开始五十步笑百步。
代码实现如下：
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}题目链接：. - 力扣（LeetCode）
三、合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
此题要求为对其合并并排序，相信有人会有这样想法：先插入在排序，其实这个方法说可以也可以，就是有点麻烦，因为这是链表不是数组，修改链表的指向，是比较麻烦的一件事。所以，我们采取以下的方法：创建一个新链表，并设立哨兵位。然后逐渐插入，把这两个链表元素值最小的进行插入，这样即可满足题目要求。 
代码实现：
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//如果List1和list2中有一个为空就直接返回另一个链表
if(list1 == NULL)
{
return list2;
}
if(list2 == NULL)
{
return list1;
}
//定义l1,l2指针分别指向list1和list2的头节点
ListNode* l1, *l2;
ListNode* newhead, *newtail;
//给新链表的开辟一个哨兵位
newhead = newtail = (ListNode*)malloc(sizeof(ListNode));
l1 = list1,l2 = list2;
while(l1 && l2)
{
if(l1->val <= l2->val)
{
newtail->next = l1;
newtail = newtail->next;
l1 = l1->next;
}
else
{
newtail->next = l2;
newtail = newtail->next;
l2 = l2->next;
}
}
if(l1)
{
newtail->next = l1;
}
if(l2)
{
newtail->next = l2;
}
//新链表的第一个节点是头节点为无效数据，因此返回头节点的next
return newhead->next;
}题目链接：. - 力扣（LeetCode）
四、分割链表
给你一个链表的头节点
head和一个特定值x，请你对链表进行分隔，使得所有 小于x的节点都出现在 大于或等于x的节点之前。你不需要 保留 每个分区中各节点的初始相对位置。
对于这道题，题目要求为大于这个值的放在一起，小于的放在一起且不需要保留相对位置。也就是说不用管排好之后的位置，就单纯的分离。现有以下思路：创建两个链表，一个放大的，一个放小的。最后，把大的放到小的后面即可。
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
if(head == NULL)
{
return NULL;
}
ListNode* greathead,*greattail;
greathead = greattail = (ListNode*)malloc(sizeof(ListNode));
ListNode* lesshead,*lesstail;
lesshead =lesstail = (ListNode*)malloc(sizeof(ListNode));
ListNode* p = head;
while(p)
{
if(p->val >= x)
{
greattail->next = p;
greattail = greattail->next;
p =p->next;
}
else
{
lesstail->next = p;
lesstail = lesstail->next;
p = p->next;
}
}
greattail->next = NULL;
lesstail->next = greathead->next;
return lesshead->next;
}题目链接：. - 力扣（LeetCode）
五、约瑟夫问题
著名的Josephus问题 据说著名犹太 Josephus有过以下的故事：在罗⻢⼈占领乔塔帕特后，39 个犹太⼈与 Josephus及他的朋友躲到⼀个洞中，39个犹太⼈决定宁愿死也不要被⼈抓到，于是决定了⼀个⾃杀 ⽅式，41个⼈排成⼀个圆圈，由第1个⼈开始报数，每报数到第3⼈该⼈就必须⾃杀，然后再由下⼀ 个重新报数，直到所有⼈都⾃杀⾝亡为⽌。 历史学家 然⽽Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与⾃⼰安排在 第16个与第31个位置，于是逃过了这场死亡游戏。
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？
数据范围： 1≤n,m≤10000
进阶：空间复杂度 O(1)，时间复杂度 O(n)
对于，约瑟夫问题大家可能会有过激反应，但是不影响做这道题，大家可参考以下思路：我们先把链表搞成一个环，然后，经行“报数”，一旦复合条件便被free掉。
typedef struct ListNode ListNode ;
ListNode* ListBuyNode(int x) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
if (node == NULL) {
exit(1);
}
node->val = x;
node->next = NULL;
return node;
}
ListNode* CreatCircle(int n) {
ListNode* phead = ListBuyNode(1);
ListNode* ptail = phead;
for (int i = 2; i <= n; i++) {
ptail->next = ListBuyNode(i);
ptail = ptail->next;
}
ptail->next = phead;
return ptail;
}
int ysf(int n, int m ) {
// write code here
ListNode* prev = CreatCircle(n);
ListNode* pcur = prev->next;
int count = 1;
while (pcur->next != pcur) {
if (count == m) {
prev->next = pcur->next;
free(pcur);
pcur = prev->next;
count = 1;
} else {
prev = pcur;
pcur = pcur->next;
count++;
}
}
return pcur->val;
}题目链接：环形链表的约瑟夫问题_牛客题霸_牛客网
六、判断链表是否有环？
给你一个链表的头节点
head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回
true。 否则，返回false。
本题可采取如下思路：运用双指针法：分为快慢指针，让它们在链表中遨游，如果能够相遇，则有环，反之，则无环。那么？有没有可能它们相遇不了，答案是：不可能！
代码实现如下：
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
{
return true;
}
}
return false;
}题目链接：. - 力扣（LeetCode）
七、求环形链表的入口点
给定一个链表的头节点
head，返回链表开始入环的第一个节点。 如果链表无环，则返回null。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
此问题与上文类似，但明显难度更大，要返回其相遇节点，大家可参考如下写法：其实相遇节点的其余部分和链表长度相同（随后会证明），我们可按照此思路，可使它们相遇，从而求出节点。
代码实现如下：
typedef struct ListNode ListNode;
struct ListNode* detectCycle(struct ListNode* head) {
ListNode *fast = head, *slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
ListNode* meet = fast;
while (head != meet) {
meet = meet->next;
head = head->next;
}
return meet;
}
}
return NULL;
}八、输入一个链表，输出该链表中倒数第k个结点
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
此题过于简单，提供一个思路：首先先定义一个链表前进k步，然后一起前进，结果就为节点值。
代码实现如下：
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k){
ListNode* p =head;
while(k--)
{
p = p->next;
}
while(p)
{
head = head->next;
p = p->next;
}
return head->val;
}题目链接：. - 力扣（LeetCode）
九、输入两个链表，找出它们的第一个公共结点
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。
本题可参考如下思路：先对这两个链表进行遍历，得出长度，求出差值，使快链表请进差值步，然后求出相遇点即为公共节点。
代码实现如下：
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
ListNode* p1 = headA;
ListNode* p2 = headB;
int count1 = 0;
int count2 = 0;
while(p1)
{
p1 = p1->next;
count1++;
}
while(p2)
{
p2 = p2->next;
count2++;
}
if(p1 != p2)
{
return NULL;
}
int nums = abs(count1 - count2);
ListNode* fast = headB;
ListNode* slow = headA;
if(count1 > count2)
{
fast = headA;
slow = headB;
}
while(nums--)
{
fast = fast->next;
}
while(fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return fast;
}题目链接：. - 力扣（LeetCode）
十、随机链表的复制
给你一个长度为
n的链表，每个节点包含一个额外增加的随机指针random，该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由
n个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的next指针和random指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。例如，如果原链表中有
X和Y两个节点，其中X.random --> Y。那么在复制链表中对应的两个节点x和y，同样有x.random --> y。返回复制链表的头节点。
声明：此题极考验链表功底，可以说此题基本上可以检验你单链表学的怎么样，如果看了此题解，能够独立写出来，便可以说掌握了单链表。
大家可参考以下思路：可以创建一个链表，进行两遍遍历，第一遍先拷贝其的值，第二遍拷贝其指向。
最后，把链表弄出来就好。
代码实现：
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {
Node* p = head;
while (p) {
Node* copy = (Node*)malloc(sizeof(Node));
copy->val = p->val;
copy->next = p->next;
p->next = copy;
p = copy->next;
}
p = head;
while (p) {
Node* copy = p->next;
if (p->random == NULL) {
copy->random = NULL;
} else {
copy->random = p->random->next;
}
p = copy->next;
}
p = head;
Node *copyhead = NULL, *copytail = NULL;
while (p) {
Node* copy = p->next;
Node* next = copy->next;
if (copyhead == NULL) {
copyhead = copytail = copy;
} else {
copytail->next = copy;
copytail = copytail->next;//精华代码
}
p->next = next;
p = next;
}
return copyhead;
}题目链接：. - 力扣（LeetCode）
最后：
本篇文章到这里就结束了，如果有不理解的题目，可私信或在评论区留下问题，记得一定要练习，这是非常重要的。再强调：大部分题目解法只为了抛砖引玉。希望对大家有所启发。
完！
![[NSSCTF]prize_p1](https://img-blog.csdnimg.cn/direct/ce7aa1b1709d45859204557b7a9c99cb.png)
