快行指针

快行指针的定义就是有两个指针访问链表，但是一个指针的速度比另外一个快，或者说一个指针在前，一个在后。

根据这个特性我们可以用来检测一个链表中是否有环。

假设：一个指针的速度是另外一个指针的两倍，它们同时开始访问同一个链表，如果链表有环的情况下，那么快行指针总会追上慢行指针，也就是总有一个时刻快行指针和慢行指针指向同一个节点，当慢行指针跑一圈的时候，快行指针此时刚好跑了两圈。

以下是具体算法：

class ListNode:Equatable {
//遵守Equatable协议
    static func == (lhs: ListNode, rhs: ListNode) -> Bool {
        if lhs.val == rhs.val && lhs.next == rhs.next{
            return true
        }else{
            return false
        }
    }
    
      public var val: Int
      public var next: ListNode?
      public init(_ val: Int) {
          self.val = val
          self.next = nil
      }
  }

class quickSolution {
    func checkCycle(_ l1:ListNode?)->Bool{
        guard let l1 = l1 else{
            return false
        }
        var slowNode:ListNode? = l1,fastNode:ListNode? = l1
        while fastNode != nil && fastNode?.next != nil {
            slowNode = slowNode?.next
            fastNode = fastNode?.next!.next
            if slowNode == fastNode {
                return true
            }
        }
        return false
    }
}

另外，我们依然可以用这个方法来解决另外一个问题。
删除链表中的第n个节点，例如：1->3->6->5->2 ，这里要删除倒数第2个节点。那么删除后的链表为： 1->3->6->2。

思路：
假设快行指针从一开始就比慢行指针快n个节点，然后他们以相同的速度前进，当快行指针走到链表的最后一个节点的时候，慢行指针的当前节点的下一个节点就是我们要删除的节点。

代码如下：

class DeleteSolution {
    func deleteNode(_ l1:ListNode?,n:Int)->ListNode?{
        guard let l1 = l1 else{
            return nil
        }
        let dummy = ListNode(0)
        dummy.next = l1
        var slowNode:ListNode? = dummy
        var fastNode:ListNode? = dummy
        //设置快行指针比慢行指针快n个节点
        for _ in 0 ..< n {
            if fastNode == nil {
                break
            }
            fastNode = fastNode?.next
        }
        
        //同时移动两个指针
        while fastNode != nil && fastNode?.next != nil {
            slowNode = slowNode?.next
            fastNode = fastNode?.next
        }
        //删除需要删除的节点
        slowNode?.next = slowNode?.next?.next
        return dummy.next
    }
}