关于链表的一些技巧

链表的结构比较简单，基本特性以及相关操作这里就不作介绍。如果有同学不自信的话，这有个pdf文档可以参考复习下。http://cslibrary.stanford.edu/103/如果有同学网络问题不给力的话，可以给我发邮件。下面来看几道常见的面试题。

1.链表倒置（两种方法）

这个应该也算比较简单的，直接上代码了。(两种：迭代、递归)

void reverse_iterate(struct node** head)
{
    struct node* result = NULL;
    struct node* current = *head;
    struct node* next;

    while(current != NULL)
    {
        next = current->next;

        current->next = result;
        result = current;
        current = next;
    }
    *head = result;
}

void reverse_recursive(struct node** head)
{
    struct node* first;
    struct node* rest;

    if(*head == NULL)
        return;

    first = head;
    rest = first->next;

    if(rest == NULL)
        return;

    reverse_recursive(& rest);

    first->next->next = first;
    first->next = NULL;

    *head = rest;
}

2.把一个链表拆为两半，要求只遍历一次

比如链表｛1，2，3，4，5｝，前半部分为｛1，2，3｝， 后半部分为｛4，5｝。如果要求只遍历一次的话，我们只需找到中间点就可以。那么我们不妨使用两个指针（point fast/low），遍历的步长一个为另一个的2倍。代码简单实现如下(已经考虑了链表长度为奇数的情况)。

void front_back_split(struct node* head, struct node** frontRef, struct node** backRef)
{
    struct node* fast;
    struct node* low;

    if(head==NULL || head->next==NULL)
    {
        *frontRef = head;
        *backRef = NULL;
    }
    else
    {
        fast = head;
        slow = head;
        while(fast != NULL)
        {
            fast = fast->next;
            if(fast != NULL)
            {
                fast = fast->next;
                slow = slow->next;
            }
        }
    }

    frontRef = head;
    backRef = slow->next;
}

3.判断一个单链表是否有环

通过第二题，同学们可能有些思路。方法是类似的。检测环的这种方法称为Floyd’s cycle finding algorithm，链接为en.wiki。方法简述一下，代码就不写了，wiki中比较详细些。设置两个指针fast,low指向表头，low每次移动一步，fast每次移动两步。如果链表不存在环，fast最终为null。如果存在环，最终两指针将在环中循环，总会相交。也就是，若两指针相交，那么单链表中存在环。

问题还没有结束，针对问题3，如何找到环的入口呢？其实这个通过数学简单思考一个就可以了。链表的长度为环的长度加上表头到入口的长度。我们可以轻松求得环的长度：fast,low指针相交后继续移动，下次相交的时候fast比low多走了一圈，又fast的速度为low的2倍。也就是说low指针移动的步数就是圈的长度（怎么有点像小学生数学应用题，小学数学V5..），记为x。将fast,low指针重置到表头，这次还是fast先移动，但是fast移动x步之后，low才开始移动，且fast和low的速度都为1，则fast和low指针再次相遇的时候就是环的入口处，想一想，是不是？