1、链表中环的入口结点

image.png

  1. 初始化：快指针fast指向头结点， 慢指针slow指向头结点
  2. 让fast一次走两步， slow一次走一步，第一次相遇在C处，停止
  3. 然后让fast指向头结点，slow原地不动，让后fast，slow每次走一步，当再次相遇，就是入口结点。


image.png

  1. /*
  2. struct ListNode {
  3.     int val;
  4.     struct ListNode *next;
  5.     ListNode(int x) :
  6.         val(x), next(NULL) {
  7.     }
  8. };  
  9. */
  10. class Solution {
  11. public:
  12.     ListNode* EntryNodeOfLoop(ListNode* pHead) {
  14.         //法一：双指针
  15.         ListNode *slow=pHead;
  16.         ListNode *fast=pHead;
  17.         while(fast && fast->next)//先快慢指针第一次相遇
  18.         {
  19.             slow=slow->next;
  20.             fast=fast->next->next;
  21.             if(slow==fast) break;
  22.         }
  23.         if(!fast || !fast->next) return nullptr;//无环的情况
  24.         fast=pHead;//快指针回到表头
  25.         while(slow!=fast)//以一样的速度再次相遇的点就是环的入口
  26.         {
  27.             slow=slow->next;
  28.             fast=fast->next;
  29.         }
  30.         return fast;
  33.         //法二 ：hashset
  34.         unordered_set<ListNode*>st;
  35.         while(pHead)
  36.         {
  37.             if(st.find(pHead)==st.end())
  38.                 st.insert(pHead),pHead=pHead->next;
  39.             else return pHead;
  40.         }
  41.         return nullptr;
  42.     }
  43. };

2、判断链表中是否有环

还是双指针，快慢指针一个一次走一步，另一个一次走两步，如果相遇，则有环。（也可以unordered_set）

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     bool hasCycle(ListNode *head) {
  12.         if(!head) return false;
  13.         ListNode *slow = head;
  14.         ListNode *fast = head;
  15.         while(fast && fast->next){
  16.             fast = fast->next->next;
  17.             slow = slow->next;
  18.             if(slow == fast) return true;
  19.         }
  20.         return false;
  21.     }
  22. };

3、合并两个排序的链表

注意，c++中申请哨兵节点可以用：new [TYPE]*

  1. /*
  2. struct ListNode {
  3.     int val;
  4.     struct ListNode *next;
  5.     ListNode(int x) :
  6.             val(x), next(NULL) {
  7.     }
  8. };*/
  9. class Solution {
  10. public:
  11.     ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
  12.         if(!pHead2) return pHead1;
  13.         if(!pHead1) return pHead2;
  14.         ListNode *head=new ListNode(0); //申请一个哨兵节点
  15.         //ListNode *head=nullptr; 段错误，混淆指针与对象，这样写是让head指向一个空指针，而不是一个节点
  16.         ListNode *ptr=head;
  17.         while(pHead1 && pHead2)
  18.         {
  19.             if(pHead1->val < pHead2->val) ptr->next=pHead1,pHead1=pHead1->next;
  20.             else ptr->next=pHead2,pHead2=pHead2->next;
  21.             ptr=ptr->next;
  22.         }
  23.         while(pHead1) ptr->next=pHead1,pHead1=pHead1->next,ptr=ptr->next;
  24.         while(pHead2) ptr->next=pHead2,pHead2=pHead2->next,ptr=ptr->next;
  25.         return head->next;
  26.     }
  27. };

4、两个链表的第一个公共结点

假如例子如下：
image.png
显然第一个公共结点为 8，但是链表 A 头结点到 8 的长度为 2，链表 B 头结点到 8 的长度为 3，显然不好办？
如果我们能够制造一种理想情况，如下：
image.png
这里先假设链表 A 头结点与结点 8 的长度 与 链表 B 头结点与结点 8 的长度相等，那么就可以用双指针。

初始化：指针 ta 指向链表 A 头结点，指针 tb 指向链表 B 头结点

如果 ta == tb， 说明找到了第一个公共的头结点，直接返回即可。
否则，ta != tb，则++ta，++tb

所以现在的问题就变成，如何让本来长度不相等的变为相等的？
假设链表 A 长度为 a， 链表 B 的长度为 b，此时 a != b
但是，a+b == b+a
因此，可以让 a+b 作为链表 A 的新长度，b+a 作为链表 B 的新长度。
如图：
image.png

  1. /*
  2. struct ListNode {
  3.     int val;
  4.     struct ListNode *next;
  5.     ListNode(int x) :
  6.             val(x), next(NULL) {
  7.     }
  8. };*/
  9. class Solution {
  10. public:
  11.     ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
  12.         ListNode *p1=pHead1, *p2=pHead2;
  13.         while(p1 != p2)
  14.         {
  15.             p1 = p1 ? p1->next : pHead2;
  16.             p2 = p2 ? p2->next : pHead1;
  17.         }
  18.         return p1;
  19.     }
  20. };

题目与题解均来源于牛客网。