一、快慢指针说明

　　快慢是指移动步数的长短，也就是每次向前移动速度的快慢。如，指定快指针每次沿着链表向前移动2步，指定慢指针每次沿着链表向前移动1步。

二、快慢指针的应用

1、判断单链表是否为循环链表

　　首先设置快慢指针的起点为链表的头结点，快指针每次向前移动2步，慢指针每次向前移动1步。如果该链表为循环链表，则快指针会在不久之后追上慢指针；如果是单链表，则快指针会先到达链表的末尾。利用快慢指针解决这个问题还有一个好处是不必预先知道链表的长度。逻辑关系简单明了：快指针追上慢指针=>循环链表，快指针到达链尾=>单链表。

1 #include
     
        2 using namespace std;  3 /* --- global variable --- */  4 int n;  5 int i;  6   7 /* --- linked list struct --- */  8 struct Node  9 { 10     int data; //node information 11     Node* next = NULL; //next pointer 12 }; 13  14 /* --- function prototypes --- */ 15 //create Circular/single linked list 16 void CreatSing(Node *&head); //'&' means to change head 17 void CreatCir(Node *&head); 18 //judge the list 19  20 void isCirOrSing(Node *head); 21  22 /* --- main function --- */ 23 int main() 24 { 25  26     //define two head 27     Node* headS = new Node(); 28     Node* headC = new Node(); 29  30     //create and judge single linked list 31     CreatSing(headS); 32     isCirOrSing(headS); 33  34     cout<
      
       <<" ---------- Luxuriant line ---------- "<
       
        <
        
          single 53         if(fast->next==NULL||fast->next->next==NULL) 54         { 55             cout<<" single linked list !"<
         
           circular 59         else if(fast->next==slow||fast->next->next==slow) 60         { 61             cout<<" circular linked list !"<
          
           next->next; //2 steps/time 67 slow = slow->next; //1 step/time 68 } 69 } 70 } 71 72 void CreatSing(Node *&head) 73 { 74 Node* p = new Node(); 75 cout<<"input linked list number: "; 76 cin>>n; 77 78 head =p; 79 cout<<"input linked list data list: "; 80 for(i=0;i
           
            >p->data; //input data 83 p->next = new Node(); 84 p = p->next; //link to next 85 } 86 cin>>p->data; 87 88 //print to check 89 cout<
            
             data<<"->"; 96 q = q->next; 97 x--; 98 } 99 cout<<"[NULL] "; //link NULL to the end100 q = NULL;101 }102 103 void CreatCir(Node *&head)104 {105 Node* p = new Node();106 cout<<"input linked list number: ";107 cin>>n;108 109 head =p;110 cout<<"input linked list data list: ";111 for(i=0;i
             
              >p->data; //input data114 if(i==n-1) //link the end to head115 p->next = head;116 else117 {118 p->next = new Node();119 p = p->next; //link to next120 }121 }122 123 //print to check124 cout<
              
               data<<"->";131 q = q->next;132 x--;133 }134 cout<<"... ";135 q = NULL;136 }
              
             
            
           
          
         
        
       
      
     

　　运行输出结果：

2、有序链表中寻找中位数

　　快指针的移动速度是慢指针的2倍，所以快指针到达链表尾巴时，慢指针到达链表中点。

　　有两种情况需要分开考虑，即链表为偶数长度时，和链表为计数长度时。（head结点依然存储数据）

　　链表长度为偶数时，快指针只能到达链表的倒数第二个结点；则慢指针的位置为上中位数；因此返回（上中位数+下中位数）/2。

　　链表长度为奇数时，快指针就能到达链表的最后一个结点；则慢指针的位置就是中位数；因此直接返回慢指针的值。

　　例如，链表长度为4时，fast第一次移动后指向倒数第二个结点（data=3），slow第一次移动后指向第二个结点（data=2）；

　　进入判断fast->next->next是否为NULL，判断成立，当前slow位置在第二个结点处（data=2），因此返回（slow->data）+（slow->next->data）/2=2.5，即为所求中位数。

　　又例如，链表长度为3时，　fast第一次移动后指向最后一个结点（data=3），slow第一次移动后指向第二个结点（data=2）；

　　进入判断fast->next是否为NULL，判断成立，当前slow位置在第二个结点处（data=2），因此返回（slow->data）=2，即为所求中位数。

　　代码实现：

1 #include
     
       2 using namespace std; 3 /* --- global variable --- */ 4 int n; 5 int i; 6  7 /* --- linked list struct --- */ 8 struct Node 9 {10     int data; //node information11     Node* next = NULL; //next pointer12 };13 14 /* --- function prototypes --- */15 void CreatSing(Node *&head); //'&' means to change head16 double findMedian(Node *head);17 18 /* --- main function --- */19 int main()20 {21     int x=2; //print twice22     while(x!=0)23     {24         x--;25 26         //define a head27         Node* head = new Node();28         //create a single linked list29         CreatSing(head);30         //find median31         double result = findMedian(head);32         //print the median33         cout<<" median = "<
      
       <
       
        next==NULL) //odd50             return (slow->data);51         else if(fast->next->next==NULL) //even52             return ((slow->data)+(slow->next->data))/2.0;53         else54         {55             fast = fast->next->next; //2 steps/time56             slow = slow->next; //1 step/time57         }58     }59 }60 61 void CreatSing(Node *&head)62 {63     Node* p = new Node();64     cout<<"input linked list number: ";65     cin>>n;66 67     head = p;68     cout<<"input linked list data list: ";69     for(i=0;i
        
         >p->data; //input data72         p->next = new Node();73         p = p->next; //link to next74     }75     cin>>p->data;76 77     //print to check78     cout<
         
          data<<"->";85         q = q->next;86         x--;87     }88     cout<<"[NULL] "; //link NULL to the end89     q = NULL;90 }
         
        
       
      
     

　　运行输出结果：