Cracking Coding Interview - 2.8 Loop Detection

2019-08-12 2 分钟阅读 ARTS-A

Loop Detection: Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop.

DEFINITION

Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.

EXAMPLE

1
2

Input:  A -> B -> C -> D -> E -> C [the same C as earlier]
Output: C

解答

这个比较复杂，结论是：

  • 弄两指针，slow每次走一步，fast每次走两步。
  • 当slow和fast相遇的时候，这个node距离【循环起点】的距离和【链表头】距离【循环起点】的距离是一样的。
  • 这个时候再从相遇点和链表头同时走，走到相遇的时候就是【循环起点】
1
2
3
4
5
6
7

o -> o -> o -> o
             /   \
            o     o
            |     |
            o     o
             \   /
               o

来看看是怎么推导出来的：

  • 假设【循环起点】到【链表头】的距离为K
  • 当slow走到【循环起点】的时候，说明它走了K，而fast则走了2K，也就是说fast已经进入【循环】走了K
  • 假设循环的长度为L，因为fast走在slow前面，所也可以说fast距离slow有L - K
  • 那么还要走多少步fast才能碰到slow呢（即遇到【交叉点】）？
    • 因为fast每次走2步，slow每次走1步，fast比slow快1步
    • 因此对于slow来说还要走L - K步才能碰到一起，对于fast来说要走2(L - K)步才能碰到一起
  • 【交叉点】的位置在哪里呢？在循环里 L -K 的位置，其实fast也在这个位置。这也就是说此交叉点距离【循环起点】为K
  • 看前面所说的，【链表头】到【循环起点】的距离同样也是K。
  • 那也就是说如果此时同时从【链表头】和【交叉点】开始走，遇到第一个相同的node，这个node就是循环的起点。
 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

public Node findLoopStart(Node a) {
  Node head = a;
  Node slow = a;
  Node fast = a;
  while (fast != null) {
    slow = slow.next;
    fast = fast.next;
    if (fast == null) {
      return null;
    }
    fast = fast.next;
    if (slow == fast) {
      // 遇到交叉点
      break;
    }
  }
  if (fast == null) {
    // 没有交叉
    return null;
  }
  while (head != null && slow != null) {
    if (head == slow) {
      // 找到循环起点
      return head;
    }
    head = head.next;
    slow = slow.next;
  }
  return null;
}
Cracking Coding Interview - 2.7 Intersection
Cracking Coding Interview - 3.1 Three in One

版权

CC BY-NC-ND 4.0

相关文章

评论