Star

LeetCode 141. Linked List Cycle

Posted on | In |

Question

Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?

Explanation

双指针，如果有重合，就说明有环。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    // Solution 1: user extra space, O(N). Time complexity:O(N). HashSet;
    // public boolean hasCycle(ListNode head) {
    //     if (head == null) return false;
    //     ListNode n = head;
    //     HashSet<ListNode> set = new HashSet<>();
    //     while(n!=null) {
    //         if (!set.contains(n)) set.add(n);
    //         else return true;
    //         n = n.next;
    //     }
    //     return false;
    // }
    // Solution 2: two pointers
    public boolean hasCycle(ListNode head) {
              if (head == null) return false;
              ListNode walker, runner;
              walker = head;
              runner = head;
              while (runner != null && runner.next != null) {
                  runner = runner.next.next;
                  walker = walker.next;
                  if (runner == walker) return true;
              }
              return false;
          }
      }
    }
}