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