在浏览列表时如何检查两个 "pointers" 是否相遇？

Question

例如，我有一个列表[1; 2; 1; 3; 2; 4; 1; 5; 6; 8;...]。该列表有重复的元素。

然后我们通过两个虚拟指针遍历列表。

一个指针 a 从头开始，速度为 2。

另一个指针 b 从列表的中间某处出发，速度为 1。

那么如何查看 a 是否与 b 会面？

例如：

a 从 [1; 2; 1; 3; 2; 4; 1; 5; 6; 8;...]

开始

b 从索引 1 开始，即 [2; 1; 3; 2; 4; 1; 5; 6; 8;...]

所以经过一次移动后，a 和 b 都会到达索引 2 并相遇。

如何仅通过元素检查是否满足，没有索引信息？

我们可以只比较两个元素的值，因为里面可能有重复的。

代码方面：

let l = [1; 2; 1; 3; 2; 4; 1; 5; 6; 8;...]

let find_middle_start l n = 
  let rec aux i = function
    | [] -> []
    | _::tl when i >= n -> tl
    | _::tl -> aux (i+1) tl
  in
  aux 0 l

let parallel_travel l =
  Random.self_init();
  let b_start = find_middle_start l (Random.int (List.length l)) in
  let rec go = function
    | [], _::_ | _::_, [] | _::[], _::_ -> print_endline "Never meet"
    | x::x1::xs, y::ys ->
      if check_meet x y then print_endline "Meet"
      else go xs ys
  in
  go l b_start

如何实施 check_meet？我不能只做 x == y 对吗？

Answer 1

绑定列表，并按身份比较它们（与==）。

| ((_::_::xs) as a)), ((_::ys) as b) ->
  if a == b then ...
  else ...

请注意，如果您试图确定一个列表是否与另一个列表共享尾部，则此方法是不够的（慢指针可以在快指针赶上它之前到达末尾）。

在浏览列表时如何检查两个 "pointers" 是否相遇？

How can I check two "pointers" meet each other when going through a list?

ocaml