链表相关问题

1, 判断单链表有没有环
2, 单链表长度为N, 找到第N/2个节点

解决这种问题的思路都是使用两个不同步长的指针遍历链表：
问题1：如果步长长的指针遇到NULL，则肯定没有环，负责两个指针必定相遇，链表存在环。可以想象一下两个人在圆形跑道跑步，一个跑的慢，一个跑的快，同时出发，还是会再次相遇的。
问题2：可以同时用步长1和步长2的两个指针遍历链表，当步长2的指针到达链表尾的时候，步长1的指针正好在中间节点

代码：

#include <stdio.h>
#include <stdlib.h>

// single list
struct _slist
{
    struct _slist *next;
    void *data;
};
typedef struct _slist slist;

// test whether there is a circle in the list
// use two pointers of different steps
// if there is a circle in the list, they will
// be the same at some point
int test_circle(slist *plist)
{
    slist *p1 = NULL;
    slist *p2 = NULL;

    if (plist == NULL)
        return 0;

    p1 = plist;
    p2 = plist->next;
    while ((p2 != NULL) && (p2 != p1))
    {
        p1 = p1->next;
        p2 = p2->next;
        if (p2 != NULL)
            p2 = p2->next;
    }

    return ((p2 == NULL) ? 0 : 1);
}

// get the middle node of the list
slist* get_middle1(slist *plist)
{
    slist *p1 = NULL;
    slist *p2 = NULL;

    if (plist == NULL)
        return NULL;

    p1 = plist;
    p2 = plist->next;
    while ((p2 != NULL) && (p2->next != NULL))
    {
        p1 = p1->next;
        p2 = p2->next->next;
    }

    return p1;
}

// get the middle node of the list
slist* get_middle2(slist *plist)
{
    slist *p1 = NULL;
    slist *p2 = NULL;
    int count;

    if (plist == NULL)
        return NULL;

    count = 0;
    p1 = plist;
    p2 = plist->next;
    while (p2 != NULL)
    {
        p2 = p2->next;
        count++;
        if ((count & 0x01) == 0)
            p1 = p1->next;
    }

    return p1;
}

slist* create_list(int n)
{
    slist *head = NULL;
    slist *tail = NULL;
    slist *tmp = NULL;
    int i = 0;

    for (i = 0; i < n; i++)
    {
        tmp = (slist*)malloc(sizeof(slist));
        if (tmp != NULL)
        {
            tmp->next = NULL;
            tmp->data = (void *)i;

            if (head == NULL)
            {
                head = tmp;
            }
            if (tail != NULL)
            {
                tail->next = tmp;
            }
            tail = tmp;
        }
    }

    return head;
}

void destroy_list(slist *plist)
{
    slist *p = plist;
    slist *tmp = NULL;
    while (p != NULL)
    {
        tmp = p;
        p = p->next;
        free(tmp);
    }
}

void print_list(slist *plist)
{
    slist *p = plist;
    while (p != NULL)
    {
        printf("%x ", p->data);
        p = p->next;
    }
}

int main(int argc, char* argv[])
{
    slist *plist1 = NULL;
    slist *plist2 = NULL;
    slist *tmp = NULL;
    slist *tail = NULL;
    int i;

    plist1 = create_list(5);
    plist2 = create_list(10);

    printf("list1: ");
    print_list(plist1);
    printf("\n");
    printf("get_middle1: %d\n", (int)(get_middle1(plist1)->data));
    printf("get_middle2: %d\n", (int)(get_middle2(plist1)->data));

    printf("list2: ");
    print_list(plist2);
    printf("\n");
    printf("get_middle1: %d\n", (int)(get_middle1(plist2)->data));
    printf("get_middle2: %d\n", (int)(get_middle2(plist2)->data));

    tmp = plist2->next->next;
    tail = plist2;
    while (tail->next != NULL)
    {
        tail = tail->next;
    }
    tail->next = tmp;

    printf("test_circle: list1, %d\n", test_circle(plist1));
    printf("test_circle: list2, %d\n", test_circle(plist2));

    tail->next = NULL;
    destroy_list(plist1);
    destroy_list(plist2);

    return 0;
}

输出：
list1: 0 1 2 3 4
get_middle1: 2
get_middle2: 2
list2: 0 1 2 3 4 5 6 7 8 9
get_middle1: 4
get_middle2: 4
test_circle: list1, 0
test_circle: list2, 1