C++將二叉樹轉為雙向鏈表及判斷兩個鏈表是否相交

把二叉查找樹轉變成排序的雙向鏈表
例如：

轉換成雙向鏈表

4=6=8=10=12=14=16struct BSTreeNode{int m_nValue; // value of nodeBSTreeNode *m_pLeft; // left child of nodeBSTreeNode *m_pRight; // right child of node};

首先闡述下二叉排序樹：

它首先要是一棵二元樹，在這基礎上它或者是一棵空樹；或者是具有下列性質的二元樹：（1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；（2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；（3）左、右子樹也分別為二元查找樹

解決思路：

中序遍歷得到的即為排序好的鏈表順序，因此需要解決的就是指針的指向問題。

好吧，我首先想到的不是遍歷過程中修改指針指向（后來看別人代碼了......）

最開始的思路是在中序遍歷過程中左孩子要訪問當前節點的父節點，因此中序遍歷過程中應當傳遞當前節點和父節點。這就導致了root（根）節點與其他節點的處理方式不同。

后來想到既然中序遍歷是一個排序好的鏈表，那么遍歷過程中將當前訪問節點的地址放入一個指針數組。遍歷結束后通過這個指針數組就可以方便的知道每個節點的前驅和后繼節點，再更改節點指向即可。

最后看到了別人的代碼，總結如下：

head指針指向鏈表表頭，index指針指向鏈表尾節點。

所有節點的左指針都指向前一節點，右指針都指向后一節點。

因此：（中間過程）

當前節點的左指針指向表尾節點；
表尾節點的右指針指向當前節點；
更新，尾節點指向當前節點；

（對于表頭，即尾節點指向NULL）,初始化Head節點。

代碼如下：

void convertToDoubleList(BSTreeNode* pCurrent){  pCurrent->m_pLeft=pIndex;  if (pIndex == NULL)  {    pHead=pCurrent;  }  else  {    pIndex->m_pRight=pCurrent;  }  pIndex=pCurrent;}

判斷倆個鏈表是否相交

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

為了簡化問題，我們假設倆個鏈表均不帶環。

問題擴展：

如果需要求出倆個鏈表相交的第一個節點列

鏈表定義

typedef struct node{  int data;  struct node * next;}List;

如果不帶環，那么分別遍歷兩個鏈表到尾節點；
若果兩個鏈表相交，那么尾節點一定相交；
如果兩個鏈表不相交，那么尾節點一定不相交；

int isJoinedNocylic(List * h1,List * h2){  while(h1 != NULL)    h1 = h1->next;  while(h2 != NULL)    h2 = h2->next;     return h1 == h2;}

如果需要求出倆個鏈表相交的第一個節點列？

網上看到了這樣的一個解法：設置兩個指針fast和slow，初始值都指向頭，slow每次前進一步，fast每次前進二步，如果鏈表存在環，則fast必定先進入環，而slow后進入環，兩個指針必定相遇。(當然，fast先行頭到尾部為NULL，則為無環鏈表)，這樣就可以判斷兩個鏈表是否相交了，程序如下：

int isCycle(List * h){  List * p1, * p2;  p1 = p2 = h;  int flag;     while(p2 != NULL && p2->next != NULL)  {    p1 = p1->next;    p2 = p2->next->next;    if(p1 == p2)    {        flag = 1;      break;    }  }     flag = 0;   return flag;}

下面看看怎么找環的入口，當fast與slow相遇時，slow肯定沒有走遍歷完鏈表，而fast已經在環內循環了n圈(1<=n)。假設slow走了s步，則fast走了2s步（fast步數還等于s 加上在環上多轉的n圈），設環長為r，則：

2s = s + nrs= nr

設整個鏈表長L，入口環與相遇點距離為x，起點到環入口點的距離為a。

a + x = nra + x = (n – 1)r +r = (n-1)r + L - aa = (n-1)r + (L – a – x)

(L – a – x)為相遇點到環入口點的距離，由此可知，從鏈表頭到環入口點等于(n-1)循環內環+相遇點到環入口點（從相遇點向后遍歷循環回到入口點的距離），于是我們從鏈表頭、與相遇點分別設一個指針，每次各走一步，兩個指針必定相遇，且相遇點為環入口點，也即為兩個鏈表的第一個相同節點。程序描述如下：

List * isJoined(List * h1,List * h2){  List * ph1,*p1,*p2;  int flag;   ph1 = h1;   while(ph1->next != NULL)    ph1 = ph1->next;    ph1->next = h2;   if(0 == isCycle(h1))  {    flag = 0;  }  else  {    p1 = h1;    while(p1 != p2)    {      p1 = p1->next;      p2 = p2->next;    }    flag = p1;  }     return flag;}