链表相关

链表结构体

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

环形链表一

给定一个链表，判断链表中是否有环。

1. 使用快慢指针，快指针一次两步，慢指针一次一步。如果链表有环则快指针一定会追上慢指针
2. 退出循环条件需要判断当前快指针是否为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。

1. 先判断有环，快指针和慢指针相遇（快指针速度为慢指针的两倍，则走过的路程也为两倍）
2. 快指针到起点，然后以和慢指针相同的速度继续前进，当第二次相遇的时候就是入环的第一个节点

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
}