链表结构体
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
环形链表一
给定一个链表,判断链表中是否有环。
- 使用快慢指针,快指针一次两步,慢指针一次一步。如果链表有环则快指针一定会追上慢指针
- 退出循环条件需要判断当前快指针是否为nil,和快指针的Next是否为nil。因为在循环体中需要用到,如果为nil会出现panic
func hasCycle(head *ListNode) bool {
if head == nil {
return false
}
for slow,fast := head,head.Next;fast != nil && fast.Next != nil ;{
if slow == fast{
return true
}
slow = slow.Next
fast = fast.Next.Next
}
return false
}
环形链表二
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
- 先判断有环,快指针和慢指针相遇(快指针速度为慢指针的两倍,则走过的路程也为两倍)
- 快指针到起点,然后以和慢指针相同的速度继续前进,当第二次相遇的时候就是入环的第一个节点
func detectCycle(head *ListNode) *ListNode {
slow,fast := head,head
for fast != nil && fast.Next !=nil{
slow = slow.Next
fast = fast.Next.Next
if slow == fast{
fast = head
for {
if fast == slow{
return fast
}
fast = fast.Next
slow = slow.Next
}
}
}
return nil
}