快慢指针的应用

快慢指针的快慢主要是指在遍历链表过程中指针移动速度的快慢。比如遍历单链表，我们可以让指针每次移动一个节点，也可以让指针移动两个或两个以上的节点。

1.单链表是否有环

如果单链表中存在环，那么快慢指针在遍历过程中相遇。就好比跑步，如果是跑圈，跑的快的人总会在某个时间与跑的慢的人相遇；如果跑道是直线，那么两个人不会相遇，但是跑的快的人最先跑到终点。

因此，使用快慢指针判断单链表是否有环也是如此。如果快指针最先遍历到链表尾部，说明没有环；如果快指针与慢指针相等即相遇，那么说明有环。

首先，创建链表节点结构体：

typedef struct Node {
    struct Node *next;
} Node, *pNode;

向链表中插入节点：

/**
 * insertNode
 * @author liebert
 * @param pNode head 链表头
 * @param pNode node 待插入节点
 * @return pNode head 新的链表头
 */
pNode insertNode(pNode head, pNode node)
{
    if (head != NULL) {
        node->next = head;
    }
    head = node;
    return head;
}

设置环节点：

/**
 * setCircle
 * @author liebert
 * @param pNode head 链表头
 * @param pNode node 循环起始的位置
 */
void setCircle(pNode head, int n)
{
    pNode p1 = head, p2;
    while (n-- > 1 && p1 != NULL) {
        p1 = p1->next;
    } 

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

}

初始化链表：

/**
 * setCircle
 * @author liebert
 * @param pNode head 链表头
 * @param int num 节点数量
 */
pNode initLinkList(pNode pHead, int num)
{
    pNode pt;
    while (num --) {
        pt = (pNode) malloc(sizeof(Node));
        pt->next = NULL;
        pHead = insertNode(pHead, pt);
    }
    return pHead;
}

判断是否有环：

/**
 * hasCircle
 * @author liebert
 * @param pNode head 链表头
 * @return int -1 链表为空 0 没有环 1 有环
 */
int hasCircle(pNode head)
{
    pNode pFast,pLow;

    if (head == NULL) return -1;    
    pFast = pLow = head;
    while(pFast->next && pFast->next->next){
        pFast = pFast->next->next;
        pLow = pLow->next;
        if (pFast == pLow) {
            return 1;
        }
    }
    return 0;
}

运行程序，查看结果：

int main ()
{
    const int NUM = 10;
    pNode pHead, pt;
    // init linklist
    pHead = initLinkList(pHead, NUM);
    printf("是否有环：%d\r\n", hasCircle(pHead));
    // set circle position
    setCircle(pHead, 4);
    printf("是否有环：%d\r\n", hasCircle(pHead));
}

2.找出环的位置

单链表如果有环，需要找出环的位置。当快慢指针第一次相遇时，让快指针从头开始，并与慢指针保持同样的速度前进，当两个指针相等时，此节点就是环的入口节点。快慢指针第一次相遇时，快指针的速度为慢指针的2倍，也就说快指针走过的路程是慢指针的2倍，对于慢指针来说是第一次走到相遇点，对于快指针来说走过了与慢指针相同的路程后还继续绕着环走了一圈，因此环的长度等于从开始位置走到相遇点的路程，即从起点到环入口的距离a加上从入口到相遇点距离b就等于环的长度l，l = a + b。同时环的长度l减去从入口到相遇点距离b是相遇点到入口点距离c，c = l –b。综上所述，慢指针从相遇点走到入口点（即走完整个环）的距离c等于从起点到环入口的距离a，此时如果此时再从链表的起点发动一个指针，速度与慢指针保持一致，那么当二者再次相遇时，慢指针第一次走完整个环，而新发动的指针也刚好走到入口点，此时指针相等，此节点就是入口节点。如下图所示：

示意图

/**
 * findCircleEntry
 * @author liebert
 * @param pNode head 链表头
 * @return int 环的位置
 */
int findCircleEntry (pNode head)
{
    pNode pFast,pLow;
    int num;

    if (head == NULL) return 0; 
    pFast = pLow = head;
    while(pFast && pFast->next){
        pFast = pFast->next->next;
        pLow = pLow->next;
        if (pFast == pLow) {
            break;
        }
    }
    if (pFast != pLow) return 0;
    pFast = head;
    num = 1;
    while (pFast != pLow) {
        pFast = pFast->next;
        pLow  = pLow->next;
        num++;
    }
    return num;
}

运行程序，查看结果：

int main ()
{
    const int NUM = 10;
    pNode pHead, pt;
    // init linklist
    pHead = initLinkList(pHead, NUM);
    printf("是否有环：%d\r\n", hasCircle(pHead));
    // set circle position
    setCircle(pHead, 4);
    printf("是否有环：%d\r\n", hasCircle(pHead));
    printf("环的位置：%d\r\n", findCircleEntry(pHead));
}

3.查找中间节点

一般地，我们通过一次遍历获得链表的长度，然后才能知道中间节点的位置，进行第二次遍历，到中间节点返回节点指针，需要做两次遍历操作。如果采取快慢指针的方式，慢指针每次移动一个节点，快指针每次移动两个节点，当快指针遍历到链表结尾时，慢指针刚好指向中间节点，具体的代码如下：

/**
 * findMiddleNode
 * @author liebert
 * @param pNode head 链表头
 * @return pNode 中间节点指针
 */
pNode findMiddleNode (pNode head)
{
    pNode pFast,pLow;

    if (head == NULL) return NULL;  
    pFast = pLow = head;
    while(pFast && pFast->next){
        pFast = pFast->next->next;
        pLow = pLow->next;
    }
    return pLow;
}