🗒️前言：
在上一期中我们给大家介绍了单链表，也了解了单链表的实现。接下来就让我们进入实践，练习一些经典题目，让我们对单链表的理解更加深入
一、链表分割
题目：
💡方法一：
我们创建两条链表，把小于x的节点放在一条链表中，剩余的放在另一条节点，最后将两条链表连接起来。在这里要使用带哨兵位的链表，不用考虑头插和第一条链表为空的问题，可以大大减少代码量。
注意：要将链表最后一个节点的指针域置为空，不然会导致链表循环。
ListNode* partition(ListNode* pHead, int x) { struct ListNode* lhead ,*ltail,*ghead,*gtail; ghead=gtail=(struct ListNode*)malloc(sizeof(struct ListNode)); lhead=ltail=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* cur=pHead; while(cur) { if(cur->val<x) { ltail->next=cur; ltail=ltail->next; } else { gtail->next=cur; gtail=gtail->next; } cur=cur->next； } ltail->next=ghead->next; gtail->next=NULL; struct ListNode* head=lhead->next; free(ghead); free(lhead); return head; }
二、链表的回文
题目：
💡方法一：
我们先找到中间节点，然后将后面的节点反转，分别从头节点和中间节点开始比较，如果两两节点的数据域有一对不相等，返回flase；如果都相等返回true。
class PalindromeList { public: //找中间节点 struct ListNode* middleNode(struct ListNode* head) { struct ListNode* fast = head; struct ListNode* slow = head; while (fast && fast->next) { fast = fast->next->next; slow = slow->next; } return slow; } //反转链表 struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur = head; struct ListNode* newnode = NULL; while (cur) { //保存节点 struct ListNode* next = cur->next; //头插 cur->next = newnode; newnode = cur; cur = next; } return newnode; } bool chkPalindrome(ListNode* head) { struct ListNode* mid=middleNode(head); struct ListNode* rmid=reverseList(mid); struct ListNode* cur=head; while(rmid&&cur) { if(rmid->val!=cur->val) { return false; } else { rmid=rmid->next; cur=cur->next; } } return true; } };
三、相交链表
题目：
💡方法一：
在做这道题，我们可以分为两步：
1.判断是否相交：
遍历两条链表，比较最后一个节点的地址，地址相等，说明两条链表相交。
2.找起始节点：
先计算出两条链表的长度，计算出它们的差值，让长的链表先走差距步，然后两条链表一起走，相等时返回的就是相交的起始节点。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* curA=headA,*curB=headB; int lenA=1,lenB=1; while(curA->next) { curA=curA->next; lenA++; } while(curB->next) { curB=curB->next; lenB++; } if(curA->next!=curB->next) { return NULL; } //求两链表的差距 int gap=abs(lenA-lenB); struct ListNode* longlist=headA,*shortlist=headB; if(lenA<lenB) { longlist=headB; shortlist=headA; } //长链表先走差距步 while(gap--) { longlist=longlist->next; } while(longlist!=shortlist) { longlist=longlist->next; shortlist=shortlist->next; } return longlist; }
四、环形链表
题目：
💡方法一：
当我们定义快慢指针，快指针一次走两步，慢指针一次走一步。如果链表存在环，在进入环中快指针一定可以追上慢指针。因为每走一步距离就减1，当减到0时就追上了。
- 假设起点到入口点距离为L
- 假设环的周长为C
- 假设入口点到相遇点的距离为X
我们通过快慢指针走过的路程来判断，但在这里要注意环的周长很小时，所以在这里要考虑两种情况：
情况一：slow进环后一圈之内，fast一定追上slow
- slow走的距离：L+X
- fast走的距离：L+C+X
情况二：slow进环时，fast已经走了n圈
- slow走的距离：L+X
- fast走的距离：L+nC+X
由于快指针速度使慢指针的二倍，所以快指针走的路程也是慢指针的二倍。由此可得出：
结论：慢指针从起点开始走，快指针从相遇点开始走，它们最终会相遇在入口点。
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* slow,* fast; slow=fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; if(fast==slow) { struct ListNode* meet=fast; while(head!=meet) { meet=meet->next; head=head->next; } return meet; } } return NULL; }
本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。你们的支持就是博主最大的动力。
