把二叉查找樹轉變成排序的雙向鏈表
例如：
轉換成雙向鏈表
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）左、右子樹也分別為二元查找樹
解決思路：
中序遍歷得到的即為排序好的鏈表順序，因此需要解決的就是指針的指向問題。
好吧，我首先想到的不是遍歷過程中修改指針指向（后來看別人代碼了......）
最開始的思路是在中序遍歷過程中左孩子要訪問當前節(jié)點的父節(jié)點，因此中序遍歷過程中應當傳遞當前節(jié)點和父節(jié)點。這就導致了root（根）節(jié)點與其他節(jié)點的處理方式不同。
后來想到既然中序遍歷是一個排序好的鏈表，那么遍歷過程中將當前訪問節(jié)點的地址放入一個指針數組。遍歷結束后通過這個指針數組就可以方便的知道每個節(jié)點的前驅和后繼節(jié)點，再更改節(jié)點指向即可。
最后看到了別人的代碼，總結如下：
head指針指向鏈表表頭，index指針指向鏈表尾節(jié)點。
所有節(jié)點的左指針都指向前一節(jié)點，右指針都指向后一節(jié)點。
因此：（中間過程）
- 當前節(jié)點的左指針指向表尾節(jié)點；
- 表尾節(jié)點的右指針指向當前節(jié)點；
- 更新，尾節(jié)點指向當前節(jié)點；
（對于表頭，即尾節(jié)點指向NULL）,初始化Head節(jié)點。
代碼如下：
void convertToDoubleList(BSTreeNode* pCurrent){ pCurrent->m_pLeft=pIndex; if (pIndex == NULL) { pHead=pCurrent; } else { pIndex->m_pRight=pCurrent; } pIndex=pCurrent;}
判斷倆個鏈表是否相交
給出倆個單向鏈表的頭指針，比如 h1，h2，判斷這倆個鏈表是否相交。
為了簡化問題，我們假設倆個鏈表均不帶環(huán)。
問題擴展：
如果需要求出倆個鏈表相交的第一個節(jié)點列
鏈表定義
typedef struct node{ int data; struct node * next;}List;
- 如果不帶環(huán)，那么分別遍歷兩個鏈表到尾節(jié)點；
- 若果兩個鏈表相交，那么尾節(jié)點一定相交；
- 如果兩個鏈表不相交，那么尾節(jié)點一定不相交；
int isJoinedNocylic(List * h1,List * h2){ while(h1 != NULL) h1 = h1->next; while(h2 != NULL) h2 = h2->next; return h1 == h2;}
如果需要求出倆個鏈表相交的第一個節(jié)點列？
網上看到了這樣的一個解法：設置兩個指針fast和slow，初始值都指向頭，slow每次前進一步，fast每次前進二步，如果鏈表存在環(huán)，則fast必定先進入環(huán)，而slow后進入環(huán)，兩個指針必定相遇。(當然，fast先行頭到尾部為NULL，則為無環(huán)鏈表)，這樣就可以判斷兩個鏈表是否相交了，程序如下：
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;} 下面看看怎么找環(huán)的入口，當fast與slow相遇時，slow肯定沒有走遍歷完鏈表，而fast已經在環(huán)內循環(huán)了n圈(1<=n)。假設slow走了s步，則fast走了2s步（fast步數還等于s 加上在環(huán)上多轉的n圈），設環(huán)長為r，則：
2s = s + nrs= nr
設整個鏈表長L，入口環(huán)與相遇點距離為x，起點到環(huán)入口點的距離為a。
a + x = nra + x = (n – 1)r +r = (n-1)r + L - aa = (n-1)r + (L – a – x)
(L – a – x)為相遇點到環(huán)入口點的距離，由此可知，從鏈表頭到環(huán)入口點等于(n-1)循環(huán)內環(huán)+相遇點到環(huán)入口點（從相遇點向后遍歷循環(huán)回到入口點的距離），于是我們從鏈表頭、與相遇點分別設一個指針，每次各走一步，兩個指針必定相遇，且相遇點為環(huán)入口點，也即為兩個鏈表的第一個相同節(jié)點。程序描述如下：
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;} 
