把二叉查找树转变成排序的双向链表
例如：
转换成双向链表
|
1
2
3
4
5
6
7
8
|
4=6=8=10=12=14=16
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
|
首先阐述下二叉排序树：
它首先要是一棵二元树，在这基础上它或者是一棵空树；或者是具有下列性质的二元树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二元查找树
解决思路：
中序遍历得到的即为排序好的链表顺序，因此需要解决的就是指针的指向问题。
好吧，我首先想到的不是遍历过程中修改指针指向（后来看别人代码了......）
最开始的思路是在中序遍历过程中左孩子要访问当前节点的父节点，因此中序遍历过程中应当传递当前节点和父节点。这就导致了root（根）节点与其他节点的处理方式不同。
后来想到既然中序遍历是一个排序好的链表，那么遍历过程中将当前访问节点的地址放入一个指针数组。遍历结束后通过这个指针数组就可以方便的知道每个节点的前驱和后继节点，再更改节点指向即可。
最后看到了别人的代码，总结如下：
head指针指向链表表头，index指针指向链表尾节点。
所有节点的左指针都指向前一节点，右指针都指向后一节点。
因此：（中间过程）
- 当前节点的左指针指向表尾节点；
- 表尾节点的右指针指向当前节点；
- 更新，尾节点指向当前节点；
（对于表头，即尾节点指向NULL）,初始化Head节点。
代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void convertToDoubleList(BSTreeNode* pCurrent)
{
pCurrent->m_pLeft=pIndex;
if (pIndex == NULL)
{
pHead=pCurrent;
}
else
{
pIndex->m_pRight=pCurrent;
}
pIndex=pCurrent;
}
|
判断俩个链表是否相交
给出俩个单向链表的头指针，比如 h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。
问题扩展：
如果需要求出俩个链表相交的第一个节点列
链表定义
|
1
2
3
4
5
|
typedef struct node
{
int data;
struct node * next;
}List;
|
- 如果不带环，那么分别遍历两个链表到尾节点；
- 若果两个链表相交，那么尾节点一定相交；
- 如果两个链表不相交，那么尾节点一定不相交；
|
1
2
3
4
5
6
7
8
9
|
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，则为无环链表)，这样就可以判断两个链表是否相交了，程序如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
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，则：
|
1
2
|
2s = s + nr
s= nr
|
设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。
|
1
2
3
|
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)
|
(L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点（从相遇点向后遍历循环回到入口点的距离），于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇点为环入口点，也即为两个链表的第一个相同节点。程序描述如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
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;
}
|