案例一:如何判断一个单链表是否有环?有环的话返回进入环的第一个节点的值,无环的话返回-1。如果链表的长度为N,请做到时间复杂度O(N),额外空间复杂度O(1)。
给定一个单链表的头结点head(注意另一个参数adjust为加密后的数据调整参数,方便数据设置,与本题求解无关),请返回所求值。
思路:快慢指针分别指向头节点,快指针每次走两个节点,慢指针每次走一个节点,如果快指针先指向空,则为无环,否则快慢指针会在环中某个节点相遇,相遇后,将快指针移到头节点,然后快慢指针每次都走一步,最终在入环点相遇。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class ChkLoop:
def chkLoop(self, head, adjust):
# write code here
slow = head
fast = head
while fast.next:
slow = slow.next
fast = fast.next.next
if not fast:
return -1
if fast==slow:
break
if not fast.next:
return -1
fast = head
while fast!=slow:
fast = fast.next
slow = slow.next
return fast # 注意题目要返回的是什么东西,盲目的
京公网安备 11010502036488号