单链表

基本结构

struct node{    ElemType data;    node *next;};

快慢指针及其应用

(1) 判断链表中是否有圈(亦称floyed判圈法)

• ACM例题: Uva 11549

  原理：两个人跑步，A的速度大于B，如果跑道没有环，那么A永远是领先于B，如果有环，那么A必然会追上B.

(2)寻找循环链表的入口

设环周期为r,相遇点为x,起点到入口长度为a,计算可得

A: a+xB: a+n*r+x因为：   Vb=2Va所以：      2(a+x)=a+n*r+x-->   a+x=n*r-->   a=n*r-x此时A回到远点重跑到入口处,Sa=aB从相遇点开始跑,Sb=x+a=n*r;n*r是环长的倍数，正好与A在入口处相遇

node *s1=head;node *s2=head;while(s1!=s2){   s1=s1->next;   if(s2->next==null) break;   s2=s2->next->next;}if(s2->next==null) return null;s1=head;while(s1!=s2){    s1=s1->next;    s2=s2->next;}return s2;

(3)寻找倒数第k个节点

两个指针保持同一速度,A指针走到k时B指针才走，那么当A指针走完整个指针时，B指针正好走到第倒数第k个节点

(4)判断两个链表相交

由于单链表的特殊性质，可知：若链表于某处相交，后面的节点都会保持一致，所以我们只需判断尾节点是否一致就可以(若两个链表都存在环，只要尾节点是环中一处即可)。