链表算法

题一、 给定单链表，检测是否有环。

        使用两个指针p1,p2从链表头开始遍历，p1每次前进一步，p2每次前进两步。如果p2到达链表尾部，说明无环，否则p1、p2必然会在某个时刻相遇(p1==p2)，从而检测到链表中有环。
/* 
* if list_a and list_b has cross point return the addrss of cross-point. 
* else return NULL 
*/ 
static List *has_cross(List *list_a, List *list_b)  
{  
    List    *pa;  
    List    *pb;  
    int     len_a, len_b;  
    int     i;  
 
    len_a = len_b = 0;  
 
    pa = list_a; /* 遍历链表a，并记录下此链表的长度 */ 
    while (pa->next != NULL) {  
        pa = pa->next;  
        len_a++;  
    }  
 
    pb = list_b; /* 遍历链表b，并记录下链表b的长度 */ 
    while (pb->next != NULL) {  
        pb = pb->next;  
        len_b++;  
    }  
 
    if (pa != pb) /* 如果指针pa，pb最后不相等，则两链表没有焦点 */ 
        return NULL;  
 
    /* 较长的链表先向后调整到第N个元素(N = max(len_a, len_b) - min(len_a, len_b)) 
然后两链表同步向后调整，同时比较地址是否相等，如果相等则为首焦点。*/ 
    pa = list_a;  
    pb = list_b;  
    if (len_a > len_b) {  
        for (i = len_a - len_b; i; i--)  
            pa = pa->next;  
    } else {  
        for (i = len_b - len_a; i; i--)  
            pb = pb->next;  
    }  
 
    while (pa != pb) {  
        pa = pa->next;  
        pb = pb->next;  
    }  
    return pa;  
} 


题二、 给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。

        如果head1==head2，那么显然相交，直接返回head1。

        否则，分别从head1,head2开始遍历两个链表获得其长度len1与len2，假设len1>=len2，那么指针p1由head1开始向后移动len1-len2步，指针p2=head2，下面p1、p2每次向后前进一步并比较p1p2是否相等，如果相等即返回该结点，否则说明两个链表没有交点。
bool IsExitsLoop(slist * head)
2 {
3     slist * slow = head ,  * fast = head;
4
5      while  ( fast  &&  fast -> next )
6      {
7          slow  =  slow -> next;
8          fast  =  fast -> next -> next;
9         if  ( slow  ==  fast )  break ;
10      }
11 
12      return   ! (fast  ==  NULL  ||  fast -> next  ==  NULL);




题三、 给定单链表(head)，如果有环的话请返回从头结点进入环的第一个节点。

        解法1:运用题一，我们可以检查链表中是否有环。

        如果有环，那么p1p2重合点p必然在环中。从p点断开环，方法为：p1=p, p2=p->next, p->next=NULL。此时，原单链表可以看作两条单链表，一条从head开始，另一条从p2开始，于是运用题二的方法，我们找到它们的第一个交点即为所求。
      解法2：
slist *  FindLoopPort(slist * head)
2 {
3     slist * slow  =  head,  * fast  =  head;
4
5     while  ( fast  &&  fast -> next )
6     {
7         slow  =  slow -> next;
8         fast  =  fast -> next -> next;
9         if  ( slow  ==  fast )  break ;
10     }
11
12     if  (fast  ==  NULL  ||  fast -> next  ==  NULL)
13         return  NULL;
14
15     slow  =  head;
16     while  (slow  !=  fast)
17     {
18          slow  =  slow -> next;
19          fast  =  fast -> next;
20     }
21
22     return  slow;
23 }
附一种易于理解的解释：

一种O（n）的办法就是（搞两个指针，一个每次递增一步，一个每次递增两步，如果有环的话两者必然重合，反之亦然）：
关于这个解法最形象的比喻就是在操场当中跑步，速度快的会把速度慢的扣圈

可以证明，p2追赶上p1的时候，p1一定还没有走完一遍环路，p2也不会跨越p1多圈才追上

我们可以从p2和p1的位置差距来证明，p2一定会赶上p1但是不会跳过p1的

因为p2每次走2步，而p1走一步，所以他们之间的差距是一步一步的缩小，4，3，2，1，0 到0的时候就重合了

根据这个方式，可以证明，p2每次走三步以上，并不总能加快检测的速度，反而有可能判别不出有环

既然能够判断出是否是有环路，那改如何找到这个环路的入口呢？

解法如下： 当p2按照每次2步，p1每次一步的方式走，发现p2和p1重合，确定了单向链表有环路了

接下来，让p2回到链表的头部，重新走，每次步长不是走2了，而是走1，那么当p1和p2再次相遇的时候，就是环路的入口了。

这点可以证明的：

在p2和p1第一次相遇的时候，假定p1走了n步骤，环路的入口是在p步的时候经过的，那么有

p1走的路径： p+c ＝ n；         c为p1和p2相交点，距离环路入口的距离

p2走的路径： p+c+k*L = 2*n；   L为环路的周长，k是整数

显然，如果从p+c点开始，p1再走n步骤的话，还可以回到p+c这个点

同时p2从头开始走的话，经过n步，也会达到p+c这点

显然在这个步骤当中p1和p2只有前p步骤走的路径不同，所以当p1和p2再次重合的时候，必然是在链表的环路入口点上。




题四、只给定单链表中某个结点p(并非最后一个结点，即p->next!=NULL)指针，删除该结点。

        办法很简单，首先是放p中数据,然后将p->next的数据copy入p中，接下来删除p->next即可。



题五、只给定单链表中某个结点p(非空结点)，在p前面插入一个结点。

        办法与前者类似，首先分配一个结点q，将q插入在p后，接下来将p中的数据copy入q中，然后再将要插入的数据记录在p中