leetcode 141. Linked List Cycle

2019-07-10 2019-09-15

leetcode

2 minutes read (About 255 words) 0 visits

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

方法1：hashtable

/**
 * 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) {
        Set set = new HashSet();
        ListNode cur = head;
        while(cur!=null && cur.next!=null){
            if(set.contains(cur.next)){
                return true;
            }
            set.add(cur.next);
            cur= cur.next;
        }
        return false;

    }
}

方法2：快慢指针

/**
 * 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) {

        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast){
                return true;
            }

        }
        return false;

    }
}

本文标题：leetcode 141. Linked List Cycle
本文作者：sanwanliu
本文链接：https://sanwanliu.github.io/2019/07/10/leetcode 141. Linked List Cycle/
发布时间：2019-07-10
版权声明：本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！

链表

Comments

Catalogue

Your browser is out-of-date!