每天一道算法题_005_找出环形链表的入口点

给定一链表头结点,如果是环形链表,返回其入口点节点。

struct ListNode
{
	int val;
	ListNode *next;
	ListNode(int num):val(num),next(nullptr){}
};

ListNode *cycleList(ListNode *head)
{
	//老规矩
	if(!head || !head->next)
		return head;
	ListNode *slow = head;
	ListNode *fast = head;
	while(fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
		if(slow == fast)
		{
			//相等 说明有环 将slow节点回退到起始位置,
			//此时 slow 距入口点的位置 和 fast 距入口点的位置长度是一样的
			//各自往后移动 相遇即可
			slow = head;
			while(true)
			{
				fast = fast->next;
				slow = slow->next;
				if(fast == slow)
				{
					return fast;
				}
			}
		}
	}
	return nullptr;
}
上一篇:260,有序链表转换二叉搜索树


下一篇:leetcode-python-无重复字符的最长子串