C語言單連結清單求環，并傳回環的起始節點

若連結清單中存在環，找出其中的環所在的節點，否則，傳回NULL

在沒有C++ set容器的優勢前提下，我們對這樣的環型的尋找以及定位可以利用快慢指針來實作。

有環的存在，類似與操場跑圈，必然存在快慢之分。有了快慢，就一定會有交點。反之，有了交點，就一定存在環。

實作過程如下：

1. slow指針移動一次，fast指針移動兩次，當fast指針和slow指針相等時保留相等時的節點
2. 根據運算，從相等時的節點和頭節點以相同的速度運算，當兩者相等時即為環的起始節點

算法實作如下：

Data *get_circle_list(Data *head) {
  Data *fast;
  Data *slow;
  fast  = head;
  slow = head;
  
  Data *meet = NULL;

  /*快速和慢速指針一起移動*/
  while (fast) {
    fast = fast -> next;
    slow = slow -> next;
    if (!fast) {//當快速指針為空時，即不存在環型節點
      return NULL;
    }
    
    //否則快速指針繼續移動
    fast = fast -> next;
    if(fast == slow) {
      meet = fast;
      break;
    }
  }
  
  /*如果沒有找到相遇的節點，那麼即不存在環型*/
  if(meet == NULL) {
    return NULL;
  } else {
    while (!(head == meet)) {
      head = head -> next;
      meet = meet -> next;
    }
    return head;
  }
  return NULL;
}      

#include <stdio.h>
#include <stdlib.h>


typedef struct link_list {
  int data;
  struct link_list *next;
}Data;

void print_list(Data *head) {
  while (head) {
    printf("%d ",head->data);
    head = head -> next;
  }
  printf("\n");
}

Data *insert_head(Data *head, int n) {
  head = (Data *)malloc (sizeof(Data));
  head -> next = NULL;
  int data;
  while(n --) {
    Data *p = (Data *)malloc(sizeof(Data));
    scanf("%d",&data);

    p -> data = data;
    p -> next = head -> next;
    head -> next = p;
  }
  return head;
}

Data *insert_tail(Data *head, int n) {
  head = (Data *)malloc(sizeof(Data));
  head -> next = NULL;
  Data *r = head;
  int data;
  while(n--) {
    Data *p = (Data *)malloc(sizeof(Data));
    scanf("%d", &data);

    p -> data = data;
    r -> next = p;
    r = p;
    p -> next = NULL;
  }
  return head;
}

Data *get_circle_list(Data *head) {
  Data *fast;
  Data *slow;
  fast  = head;
  slow = head;
  
  Data *meet = NULL;

  while (fast) {
    fast = fast -> next;
    slow = slow -> next;
    if (!fast) {
      return NULL;
    }

    fast = fast -> next;
    if(fast == slow) {
      meet = fast;
      break;
    }
  }
  
  if(meet == NULL) {
    return NULL;
  } else {
    while (!(head == meet)) {
      head = head -> next;
      meet = meet -> next;
    }
    return head;
  }
}

int main() {
  /*構造環形測試用例*/
  Data a1,a2,a3,a4,a5,a6,a7;
  a1.data = 1;
  a2.data = 2;
  a3.data = 3;
  a4.data = 4;
  a5.data = 5;
  a6.data = 6;
  a7.data = 7;

  a1.next = &a2;
  a2.next = &a3;
  a3.next = &a4;
  a4.next = &a5;
  a5.next = &a6;
  a6.next = &a7;
  /*構造環形，這裡很明顯環形的起點為5節點*/
  a7.next = &a5;

  printf("get circle node \n");
  Data *result = get_circle_list(&a1);
  printf("get circle node is %d\n",result -> data);
  return 0;
}      

get circle node 
get circle node is 5