1.相交链表(LeetCode160)

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构 。OJ链接 思路
首先，我们得判断这两个链表是否相交。如果两个链表相交，他们的尾节点的地址一定相同。想得到两个链表相交的第一个节点，有两种方法。
法1：假设a链有m个节点，b链有n个节点。用一个指针pa指向a的节点，用另一个指针pb来遍历b链，逐一判断地址是否相等。如果相等，返回这个节点的地址，不相等就让pa指向a的下一个节点，让pb继续遍历链，继续判断地址是否相等。但是这种方法的时间复杂度是O（mn）；
法2：（1）分别求两链表的长度，得出两链表的长度差，顺便判断是否相交；（2）长链表先走差距步；（3）同时走，第一个地址相同的节点就是交点。时间复杂度是O（n），空间复杂度是O（1）。

//法2
struct ListNode 
{int val;struct ListNode* next;	
}; 
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{struct ListNode* tailA = headA, * tailB = headB;int lenA = 1, lenB = 1;//为什么是1？因为当tailA和tailB指向尾节点时，停止循环，len少算了一次while (tailA->next )//为什么当tailA指向尾节点时停止循环？因为我们要判断两链表是否相交，需要尾节点的地址{lenA++;tailA = tailA->next;}while (tailB->next ){lenB++;tailB = tailB->next;}if (tailA != tailB){return NULL;}int gap = lenA - lenB;//假设A比B长struct ListNode* longList = headA;struct ListNode* shortList = headB;if (lenA < lenB){gap = lenB - lenA;longList = headB;shortList = headA;}while (gap--)//长链表先走gap步{longList = longList->next;}while (longList != shortList){longList = longList->next;shortList = shortList->next;}return longList;
}

2.环形链表(LeetCode141)

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。OJ链接

思路
使用快慢指针，慢指针走一步，快指针走两步，如果是环形链表，最终两指针会在环内相遇，这时就代表链表是环形链表。
代码

struct ListNode 
{int val;struct ListNode* next;	
};
bool hasCycle(struct ListNode* head)
{struct ListNode* slow = head, * fast = head;while (fast && fast->next)//如果没有环，fast最先指向NULL，或者fast->next指向NULL{fast = fast->next->next;slow = slow->next;if (fast == slow){return true;}}return false;
}

疑惑
（1）为什么slow走一步，fast走两步，最终会相遇？会不会错过？

（2）如果slow走m步，fast走n步，是否会相遇？

3.环形链表Ⅱ(LeetCode142)

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。OJ链接

知识准备

思路
（法1）根据以上的知识准备，我们可以先用快慢指针求出相遇点，然后让一个指针从起始点出发，另一个指针从相遇点出发，当它们相等时就可以得出入环的第一个结点。
（法2）利用快慢指针求出相遇点后，将相遇点与下一个结点断开，将问题转换成求两个链表的第一个交点。
代码

//法1
struct ListNode 
{int val;struct ListNode* next;	
};
struct ListNode* detectCycle(struct ListNode* head)
{struct ListNode* slow = head, * fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){struct ListNode* meet = slow;struct ListNode* start = head;while (meet != head){meet = meet->next;start = start->next;}return meet;}}return NULL;
}

//法2
struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{struct ListNode* tailA = headA, * tailB = headB;int lenA = 1, lenB = 1;//为什么是1？因为当tailA和tailB指向尾节点时，停止循环，len少算了一次while (tailA->next)//为什么当tailA指向尾节点时停止循环？因为我们要判断两链表是否相交，需要尾节点的地址{lenA++;tailA = tailA->next;}while (tailB->next){lenB++;tailB = tailB->next;}if (tailA != tailB){return NULL;}int gap = lenA - lenB;//假设A比B长struct ListNode* longList = headA;struct ListNode* shortList = headB;if (lenA < lenB){gap = lenB - lenA;longList = headB;shortList = headA;}while (gap--)//长链表先走gap步{longList = longList->next;}while (longList != shortList){longList = longList->next;shortList = shortList->next;}return longList;
}
struct ListNode* detectCycle(struct ListNode* head)
{struct ListNode* slow = head, * fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){struct ListNode* meet = slow;struct ListNode* list1 = meet->next;struct ListNode* list2 = head;meet->next = NULL;return getIntersectionNode(list1, list2);}}return NULL;
}