算法题/快慢指针：链表是否有环

题目

给定Singly LinkedList的头节点，编写一个函数来确定LinkedList中是否存在循环。

题解

Java

class ListNode {
  int value = 0;
  ListNode next;

  ListNode(int value) {
    this.value = value;
  }
}

class LinkedListCycle {

  public static boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {//快慢指针任何一方到达末尾时都结束
      fast = fast.next.next;
      slow = slow.next;
      if (slow == fast)
        return true; //快慢指针相遇，发现环
    }
    return false;
  }

  public static void main(String[] args) {
    ListNode head = new ListNode(1);
    head.next = new ListNode(2);
    head.next.next = new ListNode(3);
    head.next.next.next = new ListNode(4);
    head.next.next.next.next = new ListNode(5);
    head.next.next.next.next.next = new ListNode(6);
    System.out.println("LinkedList has cycle: " + LinkedListCycle.hasCycle(head));

    head.next.next.next.next.next.next = head.next.next;
    System.out.println("LinkedList has cycle: " + LinkedListCycle.hasCycle(head));

    head.next.next.next.next.next.next = head.next.next.next;
    System.out.println("LinkedList has cycle: " + LinkedListCycle.hasCycle(head));
  }
}

JavaScript

class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedListCycle {
  static hasCycle(head) {
    let slow = head;
    let fast = head;
    while (fast !== null && fast.next !== null) {
      fast = fast.next.next;
      slow = slow.next;
      if (slow === fast) {
        return true;
      }
    }
    return false;
  }
}

let head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
head.next.next.next.next.next = new ListNode(6);
console.log("LinkedList has cycle: " + LinkedListCycle.hasCycle(head));

head.next.next.next.next.next.next = head.next.next;
console.log("LinkedList has cycle: " + LinkedListCycle.hasCycle(head));

head.next.next.next.next.next.next = head.next.next.next;
console.log("LinkedList has cycle: " + LinkedListCycle.hasCycle(head));

Python

class ListNode:
    def __init__(self, value):
        self.value = value
        self.next = None


class LinkedListCycle:
    @staticmethod
    def hasCycle(head):
        slow = head
        fast = head
        while fast is not None and fast.next is not None:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                return True
        return False


head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
head.next.next.next.next.next = ListNode(6)
print("LinkedList has cycle:", LinkedListCycle.hasCycle(head))

head.next.next.next.next.next.next = head.next.next
print("LinkedList has cycle:", LinkedListCycle.hasCycle(head))

head.next.next.next.next.next.next = head.next.next.next
print("LinkedList has cycle:", LinkedListCycle.hasCycle(head))

Go

package main

import "fmt"

type ListNode struct {
	value int
	next  *ListNode
}

type LinkedListCycle struct{}

func (l *LinkedListCycle) hasCycle(head *ListNode) bool {
	slow := head
	fast := head
	for fast != nil && fast.next != nil {
		fast = fast.next.next
		slow = slow.next
		if slow == fast {
			return true
		}
	}
	return false
}

func main() {
	head := &ListNode{value: 1}
	head.next = &ListNode{value: 2}
	head.next.next = &ListNode{value: 3}
	head.next.next.next = &ListNode{value: 4}
	head.next.next.next.next = &ListNode{value: 5}
	head.next.next.next.next.next = &ListNode{value: 6}

	list := LinkedListCycle{}
	fmt.Println("LinkedList has cycle:", list.hasCycle(head))

	head.next.next.next.next.next.next = head.next.next
	fmt.Println("LinkedList has cycle:", list.hasCycle(head))

	head.next.next.next.next.next.next = head.next.next.next
	fmt.Println("LinkedList has cycle:", list.hasCycle(head))
}