一.相交鏈表

相交鏈表

相交：兩個鏈表從頭開始遍歷，尾節點一定是同一個節點。

情況一：當兩個鏈表長度相同時：

情況二：當兩個鏈表長度不同時：

思路：

1. 求兩個鏈表長度的差值gap。
2. 讓長鏈表先走gap個節點。
3. 分別遍歷兩個鏈表，比較是否為同一個節點，若是則相交，否則不相交。

代碼如下：

typedef struct ListNode ListNode;struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{ListNode* la = headA;ListNode* lb = headB;int lengthA = 0, lengthB = 0;while(la){lengthA++;//求鏈表A的長度la = la->next;}while(lb){lengthB++;//求鏈表B的長度lb = lb->next;}//求鏈表A與鏈表B長度差的絕對值int gap = abs(lengthA - lengthB);//找出長鏈表與短鏈表ListNode* longList = headA;ListNode* shortList = headB;if(lengthB > lengthA){longList = headB;shortList = headA;}//讓長鏈表先走gap個節點while(gap--){longList = longList->next;}//此時longList與shortList指針在相對的位置上（同時遍歷鏈表為NULL）//判斷兩個鏈表是否相交while(longList && shortList){if(longList == shortList){//鏈表相交return longList;}//兩個指針繼續往后走longList = longList->next;shortList = shortList->next;}//鏈表不相交return NULL;
}

二.判斷環型鏈表

環型鏈表

思路：快慢指針，即慢指針一次?一步，快指針一次走兩步，兩個指針從鏈表起始位置開始行，如果鏈表帶環則一定會在環中相遇，否則快指針率先走到鏈表的未尾。

思考1：為什么快指針每次走兩步，慢指針走一步可以相遇，有沒有可能遇不上，請推理證明！

因此，在帶環鏈表中慢指針走一步，快指針走兩步最終一定會相遇。

思考2：快指針一次走3步，走4步，…n步行嗎?

思考：真的存在N是奇數，C是偶數這一條件？？？

下面給出等式：

代碼如下：

1. 慢指針一次走一步，快指針一次走兩步

typedef struct ListNode ListNode;bool hasCycle(struct ListNode* head)
{ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){//慢指針一次走一步，快指針一次走兩步slow = slow->next;fast = fast->next->next;//當慢指針 == 快指針時，有環if (slow == fast){return true;}}//無環return false;
}

2. 慢指針一次走一步，快指針一次走三步：

typedef struct ListNode ListNode;bool hasCycle(struct ListNode *head) 
{ListNode* slow = head;ListNode* fast = head;while(fast && fast->next && fast->next->next){//慢指針一次走一步，快指針一次走三步slow = slow->next;fast = fast->next->next->next;//當慢指針 == 快指針時，有環if(slow == fast){return true;}}//無環return false;
}

三.求環型鏈表的入口節點

環型鏈表 ||

思路：快慢指針，快指針一次走兩步，慢指針一次走一步，若為環型鏈表最終在環中相遇，然后讓一個指針從相遇點開始走，一個指針從起點開始走，一次走一步，最終在進環處相遇。

代碼如下：

//解：快慢指針，快指針一次走兩步，慢指針一次走一步,若為環型鏈表最終在環中相遇//    然后讓一個指針從相遇點開始走，一個指針從起點開始走，一次走一步，最終在進環處相遇typedef struct ListNode ListNode;struct ListNode* detectCycle(struct ListNode* head)
{ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){//有環ListNode* meet = slow;//相遇點while (meet != head){//一個指針從相遇點開始走，一個指針從起點開始走，最終一定在入環點相遇head = head->next;meet = meet->next;}return meet;//入環點}}return NULL;//無環
}

typedef struct ListNode ListNode;struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{ListNode* la = headA;ListNode* lb = headB;int lengthA = 0, lengthB = 0;while(la){lengthA++;//求鏈表A的長度la = la->next;}while(lb){lengthB++;//求鏈表B的長度lb = lb->next;}//求鏈表A與鏈表B長度差的絕對值int gap = abs(lengthA - lengthB);//找出長鏈表與短鏈表ListNode* longList = headA;ListNode* shortList = headB;if(lengthB > lengthA){longList = headB;shortList = headA;}//讓長鏈表先走gap個節點while(gap--){longList = longList->next;}//此時longList與shortList指針在相對的位置上（同時遍歷鏈表為NULL）//判斷兩個鏈表是否相交while(longList && shortList){if(longList == shortList){//鏈表相交return longList;}//兩個指針繼續往后走longList = longList->next;shortList = shortList->next;}//鏈表不相交return NULL;
}struct ListNode *detectCycle(struct ListNode *head) 
{ListNode* slow = head;ListNode* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){//有環ListNode* meet = slow;//相遇點ListNode* newHead = meet->next;meet->next = NULL;return getIntersectionNode(head, newHead); }}return NULL;//無環
}