快慢指针
最近做了很多链表的题目，比如将链表逆转、查找有序链表的中位数、输出链表的倒数第K个数，接触了快慢指针这种算法思想后，发现使用快慢指针比常规的解题方法在时间性能上提升了很多，而且对于链表奇偶长度这样的情况。
快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。在有序链表中寻找中位数
设置两个快慢指针，其中快指针每次移动两个结点，慢指针每次移动一个结点，当快指针到达链表结尾时，慢指针所处的位置即链表中点处。但还要考虑链表结点个数的奇偶数，如果快指针停留在最后一个结点，那么说明链表长为奇数个，那么直接返回慢指针指向的结点即可，如果停留在倒数第二个结点，那么说明表长为偶数，则输出慢指针当前指向的结点和下一个结点数据域和的平均数即可。
while (fast && slow) { if (fast->next==NULL) return slow ->data; else if (fast->next!= NULL && fast->next->next== NULL) return (slow ->data + slow ->next->data)/2; else { fast= fast->next->next; slow = slow ->next; } }
输出链表中的倒数第K个节点(即正数第K-1个节点)
可以定义两个指针，第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第K步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个指针到达链表的尾节点时候，第二个指针正好是倒数第K个节点。
// 查找单链表中倒数第K个结点
ListNode * RGetKthNode(ListNode * pHead, unsigned int k) // 函数名前面的R代表反向
{ if(k == 0 || pHead == NULL) // 这里k的计数是从1开始的，若k为0或链表为空返回NULL
return NULL; ListNode * pAhead = pHead; ListNode * pBehind = pHead; for(int i=0;i<k-1;i++){ pAhead=pAhead->next; if(pAhead==null) return null;//当链表长度小于k时候，返回Null
} while(pAhead->next != NULL) // 前后两个指针一起向前走，直到前面的指针指向最后一个结点
{ pBehind = pBehind->next; pAhead = pAhead->next; } return pBehind; // 后面的指针所指结点就是倒数第k个结点
}
更多精彩
