环形链表
给定一个链表，判断链表中是否有环。
进阶：
你能否不使用额外空间解决此题？
思路：两个指针，一个一次前进两步一个，如果有一时刻两个相交说明有环。
时间复杂度：O(n)。两链表只需要循环一遍
空间复杂度：O(1)只需要保存两个指针
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == NULL||head->next == NULL)return false;
ListNode*a,*b;
a= head;
b = a->next;
while(true){
if(b->next == NULL)return false;
b = b->next;
if(b->next == NULL)return false;
b = b->next;
a = a->next;
if(b ==a)return true;
}
return false;
}
};
环形链表Ⅱ
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
说明：不允许修改给定的链表。
进阶：
你是否可以不用额外空间解决此题？
思路：前半部分同上题，确定有环后，两个指针继续一次2步/一次1步地前进，记录再次相遇时经过的移动的次数n，此时该次数n就为环的节点数，那么将a指向头部，将b指向a的后第n个节点，同时每次各走一步，当相遇时即为第一个入环点。
时间复杂度：O(n)。
空间复杂度：O(1)
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head == NULL||head->next == NULL)return NULL;
ListNode*a,*b;
a= head;
b = a->next;
int i=0;
while(true){
if(b->next == NULL)return NULL;
b = b->next;
if(b->next == NULL)return NULL;
b = b->next;
a = a->next;
if(b ==a){
b = b->next;
b = b->next;
a = a->next;
i++;
while(a != b){
b = b->next;
b = b->next;
a = a->next;
i++;
}
break;
}
}
a = head;
b = a;
while(i>0){
b = b->next;
i--;
}
while(a != b){
a =a->next;
b = b->next;
}
return a;
}
};
相交链表
编写一个程序，找到两个单链表相交的起始节点。
例如，下面的两个链表：
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
在节点 c1 开始相交。
注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
思路：题目只要求返回结果时保持原结构，那么耍个小聪明，运算时将a链的尾部指向b的头部，那么如果不相交就不带环，相交就变成了如上题的带环链表，交点就是入环点，所以解法如上题，先检测是否有环（是否相交），再检测入环点（相交点），最后返回的时候别忘了将链表改回来。
时间复杂度：O(n)。
空间复杂度：O(1)
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA == NULL || headB == NULL)return NULL;
ListNode*a,*b,*aa;
aa = headA;
b = headB;
while(aa->next != NULL){
aa = aa->next;
}
aa->next = b;
a= headA;
b = a->next;
int i=0;
while(true){
if(b->next == NULL){
aa->next = NULL;
return NULL;
}
b = b->next;
if(b->next == NULL){
aa->next = NULL;
return NULL;
}
b = b->next;
a = a->next;
if(b ==a){
b = b->next;
b = b->next;
a = a->next;
i++;
while(a != b){
b = b->next;
b = b->next;
a = a->next;
i++;
}
break;
}
}
a = headA;
b = a;
while(i>0){
b = b->next;
i--;
}
while(a != b){
a =a->next;
b = b->next;
}
aa->next = NULL;
return a;
}
};
