Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

141. 环形链表 #35

Closed
sailei1 opened this issue May 21, 2019 · 0 comments
Closed

141. 环形链表 #35

sailei1 opened this issue May 21, 2019 · 0 comments

Comments

@sailei1
Copy link
Owner

sailei1 commented May 21, 2019

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
image

示例 2:

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
image

示例 3:

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
image

解法:
快慢指针同时从头节点出发,慢指针一次走一步,快指针一次走两步,如果快指针追上了慢指针,证明链表中有环;否则直到快指针走到链表尾都没有追上,则链表不包含环。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */


var hasCycle = function(head) {
  let slow = head;
  let fast = slow;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      break;
    }
  }

  if (fast == null || fast.next == null) {
    return false;
  }
  
  return true
};
@sailei1 sailei1 closed this as completed May 21, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant