순환 링크 된 목록 논리

Question

/** 
* 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) { 
     if(head == null){ 
      return false; 
     } 
      ListNode slow = head; 
      ListNode fast = head.next; 

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

      } 

      return false; 
    } 
} 

순환 연결된 목록을 검색하기 위해 우리는 2 포인터 기술을 천천히 그리고 빠르게 사용합니다.

내 질문은 포인터가 순환 목록 인 경우 은이 어떤 점에서 교차해야하는지 궁금한가요?

Answer 1

시계를보세요. 그 숫자는 1에서 12까지 원형으로 표시되고 1에서 다시 원으로 돌아 간다.

큰 손은 빠르게 움직이고 작은 손은 같은 방향으로 움직이며 양쪽 모두가 천천히 움직이며 같은 지점에서 시작된다. 12).

목록 (모서리)이 원형이므로 큰 손이 결국 작은 손까지 뒤로 잡습니다. 얼마나 빨리 속도 차이에 달려 있지만 따라 잡을 것입니다. 따라 잡으면 목록은 원형이어야합니다.

따라 가지 않고 목록이 끝나면 목록이 원형이 아닙니다.

목록이 처음으로 되돌아 가지 않는 경우에도. 12가 9로 다시 돌아 가면, 빠른 손은 작은 손이 원에 들어갈 때까지 계속 돌고, 빠른 손은 결국 작은 손까지 따라 잡을 것입니다.

좋아요, 마지막 부분은 시계의 이미지가 좋지 않았지만 요점을 얻으시기 바랍니다.

Answer 2

증명이 보이는 것처럼 명확하지 않습니다.

실제로 빠른 포인터를 더 빠르게 만드는 약간의 변경으로 예 :fast = fast.next.next.next을 사용하면 알고리즘이 더 이상 작동하지 않습니다.

중요한 것은 두 포인터의 상대 속도입니다.

표준 속도에서 상대 속도는 2 - 1 = 1입니다. 즉, 각 단계에서 빠른 포인터는 한 단위를 느린 포인터에 더 가깝게 만듭니다. 이런 식으로, 그것은 빠른 하나가 따라 잡을 것이고, 다른 하나는 뛰어 넘지 않을 것이라는 것을 보장합니다.

그렇지 않으면 입니다. 상대 속도가 3 - 1 = 2이면 교차 할 수 없습니다. 이것은 포인터들 사이의 홀수 거리로 시작하고 사이클 길이가 짝수 인 경우에 발생합니다. 이 경우 거리는 항상 항상 홀수가됩니다 (따라서 0이되지 않습니다).

---

는 분명히 속도 차이에 대해 조심하지 않으면 포인터가 교차하지 않을 수 있도록 4 개 노드와 사이클에서 실행 속도 1 속도 3 빠른 포인터, 그리고 느린 포인터를 고려하려면 0 -> 1 -> 2 -> 3 -> 0과 같은 사이클을 형성하는 0, 1, 2, 3으로 라벨링된다.

초기에는 저속 포인터가 노드 0에 있고 고속 포인터가 노드 1. 이것은 강력한 가정이 아니며 초기화 방법에 관계없이 다른 초기화 전략으로 완화되지 않을 수도 있습니다.주기에 포함되지 않고 그래프에 몇 가지 추가 노드가있는 경우 일 수 있습니다 포인터가 임의로 존재할 수있게 만든다. y 위치에 도달하면).

k 단계 후에 느린 포인터는 노드 k mod 4에 있습니다. 고속 노드는 노드 (1 + 3k) mod 4에 있습니다.고속 및 저속 포인터가 동일한 위치에있는 것과 같은 k이 있다고 가정하면, 이는 (1 + 3k) mod 4 = k mod 4, , 즉(1 + 2k) mod 4 = 0을 의미합니다. 그러나 왼쪽 편이 홀수이므로 0이 될 수 없습니다. 따라서 포인터가 동일한 노드를 가리킬 수 있다는 가정은 모순으로 이어집니다.

Answer 3

글쎄, 안드레아스는 시계를 보았지만 아직 이해가 안되면 this 도울 수 있습니다. 나는 또한 당신이 머리와 빠른 포인터를 초기화해야한다고 생각 http://codecramp.com/linked-list-loop-detection/

에서 복사

public boolean isCyclic(Node first) { 
    if(first == null) { 
     return false; 
    } 
    Node fast = first; 
    Node slow = first; 
    while(fast.getNext() != null && fast.getNext().getNext() != null) { 
     slow = slow.getNext(); 
     fast = fast.getNext().getNext(); 
     if(slow == fast) { 
     return true; 
     } 
    } 
    return false; 
} 

• 코드 :

  또한, 당신은 당신의 코드를 약간 단순화 할 수 있습니다 대신 head.next