# 快慢指针

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

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

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

```  1 #include<iostream>
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 --- */
18 //judge the list
19
21
22 /* --- main function --- */
23 int main()
24 {
25
27     Node* headS = new Node();
28     Node* headC = new Node();
29
30     //create and judge single linked list
33
34     cout<<endl<<" ---------- Luxuriant line ---------- "<<endl<<endl;
35
36     //create and judge circular linked list
39
40
41     return 0;
42 }
43
44 /* ---the key function--- */
46 {
47     Node *fast; //fast pointer, 2 steps/time
48     Node *slow; //slow pointer, 1 step/time
50     while(1)
51     {
52         //fast reach NULL => single
53         if(fast->next==NULL||fast->next->next==NULL)
54         {
55             cout<<" single linked list !"<<endl;
56             break;
57         }
58         //fast catch slow => circular
59         else if(fast->next==slow||fast->next->next==slow)
60         {
61             cout<<" circular linked list !"<<endl;
62             break;
63         }
64         else
65         {
66             fast = fast->next->next; //2 steps/time
67             slow = slow->next; //1 step/time
68         }
69     }
70 }
71
73 {
74     Node* p = new Node();
75     cout<<"input linked list number: ";
76     cin>>n;
77
79     cout<<"input linked list data list: ";
80     for(i=0;i<n-1;i++)
81     {
82         cin>>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<<endl;
90     Node* q;
92     int x = 10;
93     while(q!=NULL)
94     {
95         cout<<q->data<<"->";
96         q = q->next;
97         x--;
98     }
99     cout<<"[NULL] "; //link NULL to the end
100     q = NULL;
101 }
102
104 {
105     Node* p = new Node();
106     cout<<"input linked list number: ";
107     cin>>n;
108
110     cout<<"input linked list data list: ";
111     for(i=0;i<n;i++)
112     {
113         cin>>p->data; //input data
116         else
117         {
118             p->next = new Node();
119             p = p->next; //link to next
120         }
121     }
122
123     //print to check
124     cout<<endl;
125     Node* q;
127     int x = 10; //Output the length of 10 laps
128     while(x!=0)
129     {
130         cout<<q->data<<"->";
131         q = q->next;
132         x--;
133     }
134     cout<<"... ";
135     q = NULL;
136 }```

运行输出结果：

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

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

链表长度为偶数时，快指针只能到达链表的倒数第二个结点；则慢指针的位置为上中位数；因此返回（上中位数+下中位数）/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<iostream>
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 --- */
17
18 /* --- main function --- */
19 int main()
20 {
21     int x=2; //print twice
22     while(x!=0)
23     {
24         x--;
25
27         Node* head = new Node();
28         //create a single linked list
30         //find median
32         //print the median
33         cout<<" median = "<<result<<endl;
34         cout<<endl<<" ---------- Luxuriant line ---------- "<<endl<<endl;
36     }
37
38     return 0;
39 }
40
41 /* ---the key function--- */
43 {
44     Node *fast; //fast pointer, 2 steps/time
45     Node *slow; //slow pointer, 1 step/time
47     while(1)
48     {
49         if(fast->next==NULL) //odd
50             return (slow->data);
51         else if(fast->next->next==NULL) //even
52             return ((slow->data)+(slow->next->data))/2.0;
53         else
54         {
55             fast = fast->next->next; //2 steps/time
56             slow = slow->next; //1 step/time
57         }
58     }
59 }
60
62 {
63     Node* p = new Node();
64     cout<<"input linked list number: ";
65     cin>>n;
66
68     cout<<"input linked list data list: ";
69     for(i=0;i<n-1;i++)
70     {
71         cin>>p->data; //input data
72         p->next = new Node();
73         p = p->next; //link to next
74     }
75     cin>>p->data;
76
77     //print to check
78     cout<<endl;
79     Node* q;
81     int x = 10;
82     while(q!=NULL)
83     {
84         cout<<q->data<<"->";
85         q = q->next;
86         x--;
87     }
88     cout<<"[NULL] "; //link NULL to the end
89     q = NULL;
90 }```

运行输出结果：

32 篇文章33 人订阅

0 条评论

## 相关文章

1265

3478

3853

1486

### （数据科学学习手札49）Scala中的模式匹配

Scala中的模式匹配类似Java中的switch语句，且更加稳健，本文就将针对Scala中模式匹配的一些基本实例进行介绍：

1004

### C++虚拟继承与虚基类

C++虚拟继承一般发生在多重继承的情况下。C++允许一个类有多个父类，这样就形成多重继承。多重继承使得派生类与基类的关系变得更为复杂，其中一个容易出现问题是某个...

762

793

2141

2078

1132