Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities.

preface

  • Problem 141 of LeetCode’s algorithm is to determine circular lists.
  • In fact, this problem is relatively simple, the idea is not complex, this time the Java code simple implementation.

Method 1: infinite loop

Private static Boolean test1 (ListNode head) {int I = 0; private static Boolean test1 (ListNode head) {int I = 0; boolean fal = false; ListNode next = head; while (next ! = null) { if (i > 10000000) { fal = true; break; } i++; next = next.next; } return fal; }Copy the code

Method 2: Hash table

private static boolean test2 (ListNode head) { Set<ListNode> set = new HashSet<>(); boolean fal = false; ListNode next = head; while (next ! = null) { if (set.contains(next)) { fal = true; break; } set.add(next); next = next.next; } return fal; }Copy the code

Mode 3: Dual-pointer

Private static Boolean test3 (ListNode head) {Boolean fal = false; // ListNode index = head; ListNode next = head; while (next ! = null) { ListNode toIndex; if (null == index || (toIndex = index.next) == null || (index = toIndex.next) == null) { break; } next = next.next; if (next == index) { fal = true; break; } } return fal; }Copy the code

Preparing Test data

/** * @author: ZRH * @date: 2021/10/913:57 */ public class Test1 {/** * Double pointer * * @param args */ public static void main (String[] args) throws IOException {final ListNode ListNode = buildNode(); System.out.println(" system.out. println(" system.out. println(" listNode ")); Println (" Method 2: Hash table: "+ test2(listNode)); // Method 2: hash table system.out. println(" Method 2: Hash table:" + test2(listNode)); // System.out.println(" system.out.println "+ test3(listNode)); } /** * build a list ** @return */ private static ListNode buildNode () {ListNode first = new ListNode(1); ListNode next = first; ListNode linkListNode = null; for (int i = 2; i < 100000; i++) { ListNode listNode = new ListNode(i); next.setNext(listNode); next = listNode; if (i == 70000) { linkListNode = listNode; }} // make a random ring next. SetNext (linkListNode); return first; } /** * @data private static class ListNode {private ListNode next; private Integer value; public ListNode (Integer value) { this.value = value; } @Override public int hashCode () { return value.hashCode(); }}}Copy the code

The last

  • Learn with an open mind and make progress together