【LeetCode】面试题02.04. 分割链表
原题链接：🍏分割链表🍏
题目：给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于x 的节点都出现在 大于或等于x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
本题使用带头结点的单链表更为简单，可以免去极端情况的判断（全大于等于x或全小于x）以及连接两个链表时的麻烦。
所以我们直接申请两个哨兵结点。
- 令小于x的尾插到lead的链表上；
- 令大于或等于x的尾插到ghead的链表上。
最后连接两个链表即可。
代码实现：
struct ListNode* partition(struct ListNode* head, int x) { struct ListNode* ghead,*gtail,*lhead,*ltail; struct ListNode* cur=head; ghead=gtail=(struct ListNode*)malloc(sizeof(struct ListNode)); lhead=ltail=(struct ListNode*)malloc(sizeof(struct ListNode)); while(cur) { if(cur->val<x) { ltail->next=cur;// 尾插 ltail=ltail->next; } else { gtail->next=cur;// 尾插 gtail=gtail->next; } cur=cur->next; } gtail->next=NULL;// 不置空 会导致链表进入循环 ltail->next=ghead->next;// 连接两个链表 struct ListNode* newhead=lhead->next;// 保存返回值，以便释放与返回 free(lhead); free(ghead); return newhead; }
【LeetCode】160. 相交链表
原题链接：🍏相交链表🍏
题目：给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。
该题可以利用差距步的方法，首先计算两个链表的长度，利用该长度差让长的链表先走差距步。
再同时向后走，当两个指针相等时，该位置即为交点。
代码中的假设法是一种非常值得学习的方法，大家可以自行领悟，我在代码中标识出来了。
代码实现：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* curA=headA; struct ListNode* curB=headB; int numA=1; int numB=1; while(curA->next)// 题目给定链表不为空，且两个循环结束后我们需要利用cur指针来判断是否相交，所以这里采用cur->next来判断结束 { curA=curA->next; numA++;// 由于上面循环结束条件为cur->next为空，所以这里的值少1。因此我们定义num的值为1 } while(curB->next)// 同上 { curB=curB->next; numB++;// 同上 } if(curA!=curB)// 不相交 { return NULL; } struct ListNode* longList=headA,*shortList=headB; int gap=abs(numA-numB);// 计算差距步，abs绝对值函数 if(numA<numB)// 假设法 { longList=headB; shortList=headA; } while(gap--)// 令longList走差距步 { longList=longList->next; } while(longList!=shortList) { longList=longList->next; shortList=shortList->next; } return longList; }
【LeetCode】141. 环形链表
原题链接：🍏环形链表🍏
题目：给你一个链表的头节点
head，判断链表中是否有环。如果链表中存在环 ，则返回
true。 否则，返回false。
快慢指针法：
定义两个指针。
- 一个名为slow，slow每次走一步；
- 一个名为fast，fast每次走两步。
当fast或者fast->next不为空时持续进行指针移动。
如果该链表为环形链表，那么一定存在某一时刻slow与fast相等，返回true；
如果跳出循环证明链表为非环形链表。
代码实现：
bool hasCycle(struct ListNode *head) { struct ListNode* slow=head; struct ListNode* fast=head; while(fast && fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) return true; } return false; }
【LeetCode】142. 环形链表Ⅱ
原题链接：🍏环形链表Ⅱ🍏
题目：给定一个链表的头节点
head，返回链表开始入环的第一个节点。 如果链表无环，则返回null。
方法一
与上面的思路相同，同样需要首先找到快慢指针相遇的时刻。
因为slow在一圈内必然fast会与其相遇，所以设slow在环内走了X距离。
设环外链表长度L，环的周长为C，slow进环时fast已经走了n圈，fast走的距离是slow走的距离的二倍，我们可以得到2(L+X)=L+n*C+X，即L=(n-1)*C+C-X。
如图：
结论：一个指针在相遇点meet，另一个指针为头指针，两指针同时移动，会在入环点相遇。
代码实现：
struct ListNode* detectCycle(struct ListNode* head) { struct ListNode* slow = head; struct ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { struct ListNode* meet = slow; while (head != meet) { meet = meet->next; head = head->next; } return head; } } return NULL; }
方法二
还记得上面的题目相交链表么？
我们可以将该环在相遇点meet处断开，再执行判断相交链表的函数即可。
代码实现：
//相交链表 struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) { struct ListNode* curA = headA; struct ListNode* curB = headB; int numA = 1; int numB = 1; while (curA->next)// 题目给定链表不为空，且两个循环结束后我们需要利用cur指针来判断是否相交，所以这里采用cur->next来判断结束 { curA = curA->next; numA++;// 由于上面循环结束条件为cur->next为空，所以这里的值少1。因此我们定义num的值为1 } while (curB->next)// 同上 { curB = curB->next; numB++;// 同上 } if (curA != curB)// 不相交 { return NULL; } struct ListNode* longList = headA, * shortList = headB; int gap = abs(numA - numB);// 计算差距步，abs绝对值函数 if (numA < numB)// 假设法 { longList = headB; shortList = headA; } while (gap--)// 令longList走差距步 { longList = longList->next; } while (longList != shortList) { longList = longList->next; shortList = shortList->next; } return longList; } //环形链表Ⅱ struct ListNode* detectCycle(struct ListNode* head) { struct ListNode* slow = head; struct ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { struct ListNode* meet = slow; struct ListNode* newhead = meet->next; meet->next = NULL; return getIntersectionNode(head, newhead); } } return NULL; }
