LeetCode - Algorithms - 141. Linked List Cycle

Problem

141. Linked List Cycle

Java

Two pointers

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        boolean b = false;
        ListNode slowPointer = head;
        ListNode fastPointer = head;
        while (fastPointer != null && fastPointer.next != null) {
            fastPointer = fastPointer.next.next;
            slowPointer = slowPointer.next;
            if (fastPointer != null && fastPointer.next == slowPointer) {
                b = true;
                break;
            }
        }
        return b;
    }
}

Submission Detail

  • 17 / 17 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Linked List Cycle.
  • Memory Usage: 39.3 MB, less than 12.07% of Java online submissions for Linked List Cycle.

extra space

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
import java.util.HashSet;
import java.util.Set;

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        boolean b = false;
        Set<ListNode> coll = new HashSet<ListNode>();
        ListNode node = head;
        while(node!=null) {
            if (!coll.contains(node)) {
                coll.add(node);
            }
            else {
                b = true;
                break;
            }
            node = node.next;
        }
        return b;
    }
}

Submission Detail

  • 17 / 17 test cases passed.
  • Runtime: 3 ms, faster than 19.93% of Java online submissions for Linked List Cycle.
  • Memory Usage: 39.5 MB, less than 11.80% of Java online submissions for Linked List Cycle.