系列文章目录
🎈 🎈 我的CSDN主页:OTWOL的主页，欢迎！！！👋🏼👋🏼
🎉🎉我的C语言初阶合集：C语言初阶合集，希望能帮到你！！！😍 😍
🔍🔍我的C语言进阶合集：我的C语言进阶合集，期待你的点击！！！🌈🌈
🎉🎉我的数据结构与算法合集：数据结构与算法合集，点进去看看吧！！！ 🎊🎊
😍 👋🏼🎉🎊创作不易，欢迎大家留言、点赞加收藏！！！ 🥳😁😍
文章目录
- 系列文章目录
- 一、 链表分割
- 题目描述：
- 解题思路
- 代码示例
- 二、链表的回文结构
- 题目描述：
- 解题思路
- 代码示例
- 三、相交链表
- 题目描述：
- 解题思路
- 代码示例
- 四、 环形链表
- 题目描述：
- 解题思路
- 代码示例
- 五、 返回链表开始入环的第一个节点
- 题目描述：
- 方法 1
- 代码示例
- 方法 2
- 代码示例
- END
一、 链表分割
下面是该题的链接🔗
链表分割
题目描述：
现有一链表的头指针
ListNode* pHead，给一定值x，
编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
解题思路
将所有小于给定值
x的节点 尾插到 一个带哨兵的节点，
同样地所有大于等于x的节点也 尾插到 另外一个带哨兵的节点，
最后将两个链表合并（大于等于给定值x的节点的链表 尾插到 小于给定值x的节点的链表 ）。
代码示例
// 将链表分为两部分，小于 x 的值在左边，大于等于 x 的值在右边
struct ListNode* partition(ListNode* pHead, int x)
{// 创建两个哨兵节点，分别用于存储小于 x 和大于等于 x 的节点struct ListNode* gGuard = NULL; // 大于等于 x 的节点的哨兵节点struct ListNode* lGuard = NULL; // 小于 x 的节点的哨兵节点struct ListNode* gTail = NULL; // 大于等于 x 的节点的尾节点struct ListNode* lTail = NULL; // 小于 x 的节点的尾节点// 遍历链表的当前节点struct ListNode* cur = pHead;// 为大于等于 x 的节点分配一个哨兵节点struct ListNode* tmp1 = (struct ListNode*)calloc(1,sizeof(struct ListNode));if (tmp1 == NULL) {perror("calloc fail"); // 如果内存分配失败，打印错误信息return NULL;}gGuard = gTail = tmp1; // 初始化哨兵节点和尾节点gTail->next = NULL; // 哨兵节点的下一个节点设置为 NULL// 为小于 x 的节点分配一个哨兵节点struct ListNode* tmp2 = (struct ListNode*)calloc(1,sizeof(struct ListNode));if (tmp2 == NULL) {perror("calloc fail"); // 如果内存分配失败，打印错误信息return NULL;}lGuard = lTail = tmp2; // 初始化哨兵节点和尾节点lTail->next = NULL; // 哨兵节点的下一个节点设置为 NULL// 遍历原始链表while(cur){// 如果当前节点 cur 的值小于 x，将其接到小于 x 的链表后面if (cur->val < x) {lTail->next = cur;lTail = lTail->next;}// 否则，将其接到大于等于 x 的链表后面else {gTail->next = cur;gTail = gTail->next;}// 当前节点 cur 移动到下一个节点cur = cur->next;}// 将大于等于 x 的链表接到小于 x 的链表后面gTail->next = NULL; // 确保大于等于 x 的链表尾部为空（即没有下一个节点）// 将两个链表合并lTail->next = gGuard->next;// 更新头节点为小于 x 的链表的头节点pHead = lGuard->next;// 释放两个哨兵节点占用的内存free(lGuard);free(gGuard);// 将哨兵节点指针设置为 NULL，避免野指针lGuard = NULL;gGuard = NULL; // 返回新的头节点return pHead;
}
二、链表的回文结构
下面是该题的链接🔗
链表的回文结构
题目描述：
对于一个链表，请设计一个时间复杂度为
O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
解题思路
第一步：先找到链表的 中间节点；
第二步：逆序 后半部分链表；
第三步：判断前半部分 和 后半部分的 节点值 是否 一 一 对应相等。
代码示例
- 寻找链表的中间节点
// 寻找链表的中间节点
struct ListNode* middleNode(struct ListNode* head)
{// 使用快慢指针法，fast 每次走两步，slow 每次走一步struct ListNode* fast = head;struct ListNode* slow = head;// 当 fast 指针和 fast 的下一个节点都不为空时，继续循环while( (fast != NULL) && (fast->next != NULL)){// 快指针 fast 走两步fast = fast->next->next;// 慢指针 slow 走一步slow = slow->next;}// 当 fast 指针到达链表末尾时，slow 指针即为中间节点return slow;
}
- 逆序链表
// 逆序链表
struct ListNode* reverseList(struct ListNode* head)
{// 新的头节点初始化为 NULLstruct ListNode* newHead = NULL;// 从原始链表的头节点开始遍历struct ListNode* cur = head;struct ListNode* next = NULL;// 遍历原始链表while(cur != NULL){// 保存当前节点的下一个节点next = cur->next;// 将当前节点的 next 指向新的头节点，实现逆转cur->next = newHead;// 将新的头节点位置移动到当前节点newHead = cur;// 移动到下一个节点（实际上是原链表的下一个节点）cur = next;}// 返回新链表的头节点return newHead;
}
- 检查链表是否为回文链表
// 检查链表是否为回文链表
bool chkPalindrome(struct ListNode* head)
{// 首先找到链表的 中间节点struct ListNode* MidNode = middleNode(head);// 然后 逆序 后半部分链表struct ListNode* rhead = reverseList(MidNode);// 使用两个指针，一个从头节点开始，一个从逆序后的后半部分链表开始// 比较两个链表的节点值是否相同while (rhead != NULL) {// 如果对应的节点值不相等，则链表不是回文链表，返回 falseif ((rhead->val) != (head->val)) {return false;}// 移动两个指针到下一个节点，继续比较rhead = rhead->next;head = head->next; }// 如果所有对应的节点值都 相等，链表是回文链表，返回 truereturn true;
}
三、相交链表
下面是该题的链接🔗
相交链表
题目描述：
给你两个单链表的头节点
headA和headB，
请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。
解题思路
代码示例
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
// 定义一个函数，用于找到两个链表的起始交点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{// 初始化两个指针，分别指向两个链表的头节点struct ListNode *tailA = headA;struct ListNode *tailB = headB;// 初始化两个变量，用于存储两个链表的长度int lenA = 0;int lenB = 0;// 计算链表 A 的长度while(tailA){tailA = tailA->next;++lenA; // 链表 A 的长度加 1}// 计算链表 B 的长度while(tailB){tailB = tailB->next;++lenB; // 链表 B 的长度加 1}// 如果两个链表在遍历结束后指针不相等，则说明没有交点，返回 NULLif(tailA != tailB){return NULL;}// 计算两个链表长度的差值int gap = abs(lenA - lenB); // 使用标准库函数 abs 计算绝对值// 初始化两个指针，分别指向两个链表的头节点，用于后续的遍历struct ListNode * LongList = headA;struct ListNode * ShortList = headB;// 根据两个链表的长度，确定哪个链表更长，哪个更短if(lenA < lenB){LongList = headB; // 如果链表 B 更长，则交换指针ShortList = headA;}// 让长链表的指针先走，直到两个链表的长度相等while(gap--){LongList = LongList->next; // 长链表的指针向前移动}// 同时遍历两个链表，直到它们相遇while(LongList != ShortList){LongList = LongList->next; // 长链表的指针向前移动ShortList = ShortList->next; // 短链表的指针向前移动}// 如果两个链表有交点，则返回起始交点的节点return ShortList;
}
四、 环形链表
下面是该题的链接🔗
环形链表
题目描述：
给你一个链表的头节点
head，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。
解题思路
代码示例
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
// 定义一个函数，用于判断链表中是否存在环
bool hasCycle(struct ListNode *head)
{// 初始化两个指针，slow 和 fast，都指向链表的头节点struct ListNode * slow = head;struct ListNode * fast = head;// 使用快慢指针法来判断链表是否有环// 快指针 fast 每次移动两步，慢指针 slow 每次移动一步while(fast && fast->next) // 确保 fast 和 fast->next 都不为空{fast = fast->next->next; // 快指针移动两步slow = slow->next; // 慢指针移动一步// 如果快慢指针相遇，则链表有环，返回 trueif(slow == fast){return true;}}// 如果 fast 指针已经到达链表末尾或者 fast->next 为空，说明链表没有环，返回 falsereturn false;
}
五、 返回链表开始入环的第一个节点
下面是该题的链接🔗
返回链表开始入环的第一个节点
题目描述：
给定一个链表的头节点
head，返回链表开始入环的第一个节点。
如果链表无环，则返回NULL。
方法 1
代码示例
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/// 定义一个函数，用于找到两个链表的起始交点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{// 初始化两个指针，分别指向两个链表的头节点struct ListNode *tailA = headA;struct ListNode *tailB = headB;// 初始化两个变量，用于存储两个链表的长度int lenA = 0;int lenB = 0;// 计算链表 A 的长度while(tailA){tailA = tailA->next;++lenA; // 链表 A 的长度加 1}// 计算链表 B 的长度while(tailB){tailB = tailB->next;++lenB; // 链表 B 的长度加 1}// 如果两个链表在遍历结束后指针不相等，则说明没有交点，返回 NULLif(tailA != tailB){return NULL;}// 计算两个链表长度的差值int gap = abs(lenA - lenB); // 使用标准库函数 abs 计算绝对值// 初始化两个指针，分别指向两个链表的头节点，用于后续的遍历struct ListNode * LongList = headA;struct ListNode * ShortList = headB;// 根据两个链表的长度，确定哪个链表更长，哪个更短if(lenA < lenB){LongList = headB; // 如果链表 B 更长，则交换指针ShortList = headA;}// 让长链表的指针先走，直到两个链表的长度相等while(gap--){LongList = LongList->next; // 长链表的指针向前移动}// 同时遍历两个链表，直到它们相遇while(LongList != ShortList){LongList = LongList->next; // 长链表的指针向前移动ShortList = ShortList->next; // 短链表的指针向前移动}// 如果两个链表有交点，则返回起始交点的节点return ShortList;
}// 定义一个函数，用于检测链表中的环，并返回环的起始节点
struct ListNode *detectCycle(struct ListNode *head)
{// 初始化两个指针，slow 和 fast，都指向链表的头节点struct ListNode *slow = head;struct ListNode *fast = head;// 使用快慢指针法来检测链表是否有环while(fast && fast->next) // 确保 fast 和 fast->next 都不为空{fast = fast->next->next; // 快指针移动两步slow = slow->next; // 慢指针移动一步// 如果快慢指针相遇，说明链表有环if(fast == slow){// 找到相遇点，将 meet 指针指向相遇节点struct ListNode *meet = slow;// 初始化两个指针，List1 指向链表头节点，List2 指向相遇点的下一个节点struct ListNode *List1 = head;struct ListNode *List2 = meet->next;// 从相遇点断开环，将相遇节点的 next 指针设置为 NULLslow->next = NULL; // 返回环的起始节点，通过调用 getIntersectionNode函数找到两个链表的交点return getIntersectionNode(List1, List2);}}// 如果 fast 指针已经到达链表末尾或者 fast->next 为空，说明链表没有环，返回 NULLreturn NULL;
}
方法 2
结论法：
如果链表存在环，则一个指针从相遇点出发，另外一个指针从链表的头节点出发，两个指针会在入环的第一个节点相遇。
代码示例
// 定义一个函数 detectCycle，用于检测链表中是否存在环，并返回环的起始节点。
struct ListNode *detectCycle(struct ListNode *head)
{// 初始化两个指针，fast 和 slow，都指向链表的头节点。struct ListNode * fast = head;struct ListNode * slow = head;// 使用快慢指针法来检测环。// 快指针 fast 每次移动两步，慢指针 slow 每次移动一步。while(fast && fast->next){// 移动 fast 指针两步fast = fast->next->next;// 移动 slow 指针一步slow = slow->next;// 如果 fast 和 slow 相遇，则链表中存在环。if(slow == fast){// 找到相遇点，将 meet 指针指向相遇点。struct ListNode * meet = slow;// 初始化两个指针，List1 指向相遇点，List2 指向头节点。// 这两个指针将用于找到环的起始节点。struct ListNode * List1 = meet;struct ListNode * List2 = head;while(List2 != List1){// List1 和 List2 每次各移动一步，直到它们相遇。// 相遇点 即为环的起始节点。List1 = List1->next;List2 = List2->next;}// 返回入环后的 起始节点。return List1;}}// 如果没有检测到环，则返回 NULL。return NULL;
}
END
每天都在学习的路上！
On The Way Of Learning
