142. Linked List Cycle II
给定一个linked list,如果存在循环,回传循环开始的node;无循环则回传Null。
如果串行中有存在一些节点可以借由一直跟着指标 next 走而重复抵达的话,则代表该连
结串行中有环。测资中,pos 将代表尾端连结到的连结串行中之位置(索引值从 0 开始
)。如果 pos 为 -1 ,则连结串行中无环。注意到,pos 实际上并不会作为参数传入。
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the
second node.
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the
first node.
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.
思路:
又是使用fast & slow pointer的题目。
为了避免出现空指标,先设定fast与fast->next不为NULL,之后开始跑循环,
找到slow == fast即可跳出循环。
第二步确认是否有循环,如无循环,回传NULL。
最后,使head跑到与slow的交会处,此处即为循环起始点,回传head。
C Code