Question

面试题 02.08. 环路检测

English Version

题目描述

给定一个有环链表，实现一个算法返回环路的开头节点。
有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

进阶：
你是否可以不用额外空间解决此题？

解法

方法一

# Definition for singly-linked list.
# class ListNode:
#   def __init__(self, x):
#     self.val = x
#     self.next = None


class Solution:
  def detectCycle(self, head: ListNode) -> ListNode:
    slow = fast = head
    has_cycle = False
    while not has_cycle and fast and fast.next:
      slow, fast = slow.next, fast.next.next
      has_cycle = slow == fast
    if not has_cycle:
      return None
    p = head
    while p != slow:
      p, slow = p.next, slow.next
    return p

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   int val;
 *   ListNode next;
 *   ListNode(int x) {
 *     val = x;
 *     next = null;
 *   }
 * }
 */
public class Solution {
  public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    boolean hasCycle = false;
    while (!hasCycle && fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
      hasCycle = slow == fast;
    }
    if (!hasCycle) {
      return null;
    }
    ListNode p = head;
    while (p != slow) {
      p = p.next;
      slow = slow.next;
    }
    return p;
  }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    bool hasCycle = false;
    while (!hasCycle && fast && fast->next) {
      slow = slow->next;
      fast = fast->next->next;
      hasCycle = slow == fast;
    }
    if (!hasCycle) {
      return nullptr;
    }
    ListNode* p = head;
    while (p != slow) {
      p = p->next;
      slow = slow->next;
    }
    return p;
  }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *   Val int
 *   Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
  slow, fast := head, head
  hasCycle := false
  for !hasCycle && fast != nil && fast.Next != nil {
    slow, fast = slow.Next, fast.Next.Next
    hasCycle = slow == fast
  }
  if !hasCycle {
    return nil
  }
  p := head
  for p != slow {
    p, slow = p.Next, slow.Next
  }
  return p
}

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  let slow = head;
  let fast = head;
  let hasCycle = false;
  while (!hasCycle && fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    hasCycle = slow == fast;
  }
  if (!hasCycle) {
    return null;
  }
  let p = head;
  while (p != slow) {
    p = p.next;
    slow = slow.next;
  }
  return p;
};