# Linked List Cycle

> Given a linked list, determine if it has a cycle in it.

> Can you solve it without using extra space?

```c++
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == NULL || head->next == NULL) {
return false;
}

ListNode* fast = head;
ListNode* slow = head;

while(fast->next != NULL && fast->next->next != NULL) {
fast = fast->next->next;
slow = slow->next;
if(slow == fast) {
return true;
}
}

return false;
}
};
```

# Linked List Cycle II

> Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

> Can you solve it without using extra space?

```
n6-----------n5
| |
n1--- n2---n3--- n4|

```

```c++
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head == NULL || head->next == NULL) {
return NULL;
}

ListNode* fast = head;
ListNode* slow = head;

while(fast->next != NULL && fast->next->next != NULL) {
fast = fast->next->next;
slow = slow->next;
if(fast == slow) {
while(slow != fast) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
}

return NULL;
}
};
```

# Intersection of Two Linked Lists

> Write a program to find the node at which the intersection of two singly linked lists begins.

> For example, the following two linked lists:

>```
A: a1 → a2

c1 → c2 → c3

B: b1 → b2 → b3
```
begin to intersect at node c1.

> Notes:

> + If the two linked lists have no intersection at all, return null.
> + The linked lists must retain their original structure after the function returns.
> + You may assume there are no cycles anywhere in the entire linked structure.
> + Your code should preferably run in O(n) time and use only O(1) memory.

+ 遍历A，到结尾之后，将A最后的节点连接到B的开头，也就是`c3 -> b1`
+ 使用两个指针fast和slow，从a1开始，判断是否有环
+ 如果没环，在返回之前记得将`c3 -> b1`给断开
+ 如果有环，则按照第二题的解法得到c1，然后断开`c3 -> b1`

```c++
class Solution {
public:
return NULL;
} else if (!headB) {
return NULL;
}

ListNode* p = headA;
while(p->next) {
p = p->next;
}

//将两个链表串起来

ListNode* tail = p;

//fast和slow，判断是否有环
break;
}
}

//没环，断开两个链表
tail->next = NULL;
return NULL;
}

//有环，得到环的起点