带环链表

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

解题

定义两个指针p1 p2

p1每次向前走一步

p2每次向前走两步

当p2能赶上p1的时候说明有环

/** * Definition for ListNode. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int val) { *         this.val = val; *         this.next = null; *     } * } */ public class Solution {    /**     * @param head: The first node of linked list.     * @return: True if it has a cycle, or false     */    public boolean hasCycle(ListNode head) {          // write your code here        if(head == null || head.next == null)            return false;        ListNode p1 = head;        ListNode p2 = head;        p2 = p2.next;        while(p2.next!=null && p2.next.next!=null){            if(p1 == p2){                return true;            }            p1 = p1.next;            p2 = p2.next.next;        }        return false;    }}

 

1 """ 2 Definition of ListNode 3 class ListNode(object): 4  5     def __init__(self, val, next=None): 6         self.val = val 7         self.next = next 8 """ 9 class Solution:10     """11     @param head: The first node of the linked list.12     @return: True if it has a cycle, or false13     """14     def hasCycle(self, head):15         # write your code here16         if head == None or head.next == None:17             return False18         slow = head19         fast = head20         fast = fast.next21         while fast.next!=None and fast.next.next!=None:22             if fast == slow:23                 return True24             else:25                 slow = slow.next26                 fast = fast.next.next27         return False