小米面试的时候遇到的一个有关问题，求大神分析
小米面试的时候遇到的一个问题，求大神分析
前一段时间小米面试的时候大牛给出了这么一道题：一个双向链表，其中某个节点的一个指针指错了，写一个程序将错误的指针修改过来。
个人分析：指针指错有四种可能：该节点的前驱指针向前指错，前驱指针向后指；后继指针向前指，后继指针向后指错。应该是这四种情况，当怎么进行判断和修改呢？还请大神们指教
------解决方案--------------------
首先，我们要明确，指针出错并不只是楼主所说的4种可能，而是可以任意指向错误的地方。
其次，错误指针指向的位置，可能位于链表外，但是那块内存的值正好指向了链表本身（错误的内存值的可能性是无限的）。
第三，这个双向链表的长度是有限的，并且头尾的位置我们是知道的（如果头尾都不知道，就没法判断了）。
第四，由于双向链表的对称性，这个问题可能有两个解。
1 边界判断
链表为空，那也就无所谓错了，题目的要求说明链表不为空
if( headNode->prev != NULL ) 找到了
if( tailNode->next != NULL ) 找到了
if( headNode == tailNode ) 必然是上面两种情况之一
2 中间判断
从头部向尾部扫描，构造一个辅助哈希表1（放入headNode）。从尾部向头部扫描，构造哈希表2（放入tailNode）。两个扫描交替进行。
每次扫描，探测下个节点，如符合双向链表规则就放入自己的哈希表，否则就探测节点是否出现在对方的哈希表中，如出现，则修改这个节点就好了。
因为只有一个指针是错误的，所以某一个方向是正常的，必然会碰上另一个方向的某个节点。
------解决方案--------------------
构造哈希表就是为了保留两个方向遍历过的节点，这样可以在两个方向相遇时做判断。
a <- b = c = d = e = f
||
g
||
h
||
i
||
j
||
k
||
l
如上图，( =和|| 都代表两个方向的指针 )假设a和f是正确的头尾，但是a的后继指错了，指向了g（我们假设g-l这些节点不是我们想要的），而g恰好也是双向列表节点，g的前驱是a。
那么从a向后遍历就会进入一条“错误通道”，不会再碰到本链表的节点，而从f向前遍历就会进入正确通道，并且会在a，b之间发现问题。
前一段时间小米面试的时候大牛给出了这么一道题：一个双向链表，其中某个节点的一个指针指错了，写一个程序将错误的指针修改过来。
个人分析：指针指错有四种可能：该节点的前驱指针向前指错，前驱指针向后指；后继指针向前指，后继指针向后指错。应该是这四种情况，当怎么进行判断和修改呢？还请大神们指教
------解决方案--------------------
首先，我们要明确，指针出错并不只是楼主所说的4种可能，而是可以任意指向错误的地方。
其次，错误指针指向的位置，可能位于链表外，但是那块内存的值正好指向了链表本身（错误的内存值的可能性是无限的）。
第三，这个双向链表的长度是有限的，并且头尾的位置我们是知道的（如果头尾都不知道，就没法判断了）。
第四，由于双向链表的对称性，这个问题可能有两个解。
1 边界判断
链表为空，那也就无所谓错了，题目的要求说明链表不为空
if( headNode->prev != NULL ) 找到了
if( tailNode->next != NULL ) 找到了
if( headNode == tailNode ) 必然是上面两种情况之一
2 中间判断
从头部向尾部扫描，构造一个辅助哈希表1（放入headNode）。从尾部向头部扫描，构造哈希表2（放入tailNode）。两个扫描交替进行。
每次扫描，探测下个节点，如符合双向链表规则就放入自己的哈希表，否则就探测节点是否出现在对方的哈希表中，如出现，则修改这个节点就好了。
因为只有一个指针是错误的，所以某一个方向是正常的，必然会碰上另一个方向的某个节点。
------解决方案--------------------
构造哈希表就是为了保留两个方向遍历过的节点，这样可以在两个方向相遇时做判断。
a <- b = c = d = e = f
||
g
||
h
||
i
||
j
||
k
||
l
如上图，( =和|| 都代表两个方向的指针 )假设a和f是正确的头尾，但是a的后继指错了，指向了g（我们假设g-l这些节点不是我们想要的），而g恰好也是双向列表节点，g的前驱是a。
那么从a向后遍历就会进入一条“错误通道”，不会再碰到本链表的节点，而从f向前遍历就会进入正确通道，并且会在a，b之间发现问题。