鏈表相交（及相交的節點）、判斷鏈表是否有環問題

鏈表相交問題
給出倆個單向鏈表的頭指針，比如h1，h2，判斷這倆個鏈表是否相交。

解決方案：
1.先判斷鏈表是否有環
2.沒有環，兩個鏈表都遍歷到最後的節點，判斷這連個節點是否相同。
3.有環，必定相交。
[cpp]
struct Node { 
  int data; 
  int Node *next; 
}; 
// if there is no cycle.  
int isJoinedSimple(Node * h1, Node * h2) { 
  while (h1->next != NULL) { 
    h1 = h1->next; 
  } 
  while (h2->next != NULL) { 
    h2 = h2-> next; 
  } 
  return h1 == h2; 
} 
// if there could exist cycle  
int isJoined(Node *h1, Node * h2) { 
  Node* cylic1 = testCylic(h1); 
  Node* cylic2 = testCylic(h2); 
  if (cylic1+cylic2==0) return isJoinedSimple(h1, h2); 
  if (cylic1==0 && cylic2!=0 || cylic1!=0 &&cylic2==0) return 0; 
  Node *p = cylic1; 
  while (1) { 
    if (p==cylic2 || p->next == cylic2) return 1; 
    p=p->next->next; 
    cylic1 = cylic1->next; 
    if (p==cylic1) return 0; 
  } 
} 
Node* testCylic(Node * h1) { 
  Node * p1 = h1, *p2 = h1; 
  while (p2!=NULL && p2->next!=NULL) { 
    p1 = p1->next; 
    p2 = p2->next->next; 
    if (p1 == p2) { 
      return p1; 
    } 
  } 
  return NULL; 
} 

struct Node {
  int data;
  int Node *next;
};
// if there is no cycle.
int isJoinedSimple(Node * h1, Node * h2) {
  while (h1->next != NULL) {
    h1 = h1->next;
  }
  while (h2->next != NULL) {
    h2 = h2-> next;
  }
  return h1 == h2;
}
// if there could exist cycle
int isJoined(Node *h1, Node * h2) {
  Node* cylic1 = testCylic(h1);
  Node* cylic2 = testCylic(h2);
  if (cylic1+cylic2==0) return isJoinedSimple(h1, h2);
  if (cylic1==0 && cylic2!=0 || cylic1!=0 &&cylic2==0) return 0;
  Node *p = cylic1;
  while (1) {
    if (p==cylic2 || p->next == cylic2) return 1;
    p=p->next->next;
    cylic1 = cylic1->next;
    if (p==cylic1) return 0;
  }
}
Node* testCylic(Node * h1) {
  Node * p1 = h1, *p2 = h1;
  while (p2!=NULL && p2->next!=NULL) {
    p1 = p1->next;
    p2 = p2->next->next;
    if (p1 == p2) {
      return p1;
    }
  }
  return NULL;
}鏈表無環求相交鏈表的第一個共同節點
解決方案：
方法1：利用兩次循環

方法2：標記已經訪問的節點

方法3：利用A和B節點數目之差  
1）計算出鏈表A的節點數目，記做c1；

2）計算出鏈表B的節點數目，記做c2；

3）算出節點數目之差：d = abs(c1 - c2)；

4）現在從節點數較多的鏈表開始，從頭往前走過d個節點，從此節點往前走，兩個鏈表有相同數目的節點。

5）此時我們可以同時遍歷兩個鏈表直到找到一個交點。

這個算法的復雜度是O(m+n)，是推薦使用的方法。