快慢指针
一、快慢指针说明
快慢是指移动步数的长短，也就是每次向前移动速度的快慢。如，指定快指针每次沿着链表向前移动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 --- */
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<<endl<<" ---------- Luxuriant line ---------- "<<endl<<endl;
35
36 //create and judge circular linked list
37 CreatCir(headC);
38 isCirOrSing(headC);
39
40
41 return 0;
42 }
43
44 /* ---the key function--- */
45 void isCirOrSing(Node *head)
46 {
47 Node *fast; //fast pointer, 2 steps/time
48 Node *slow; //slow pointer, 1 step/time
49 fast = slow = head; //start at head
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
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<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;
91 q = head;
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
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<n;i++)
112 {
113 cin>>p->data; //input data
114 if(i==n-1) //link the end to head
115 p->next = head;
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;
126 q = head;
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倍，所以快指针到达链表尾巴时，慢指针到达链表中点。
有两种情况需要分开考虑，即链表为偶数长度时，和链表为计数长度时。（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<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 --- */
15 void CreatSing(Node *&head); //'&' means to change head
16 double findMedian(Node *head);
17
18 /* --- main function --- */
19 int main()
20 {
21 int x=2; //print twice
22 while(x!=0)
23 {
24 x--;
25
26 //define a head
27 Node* head = new Node();
28 //create a single linked list
29 CreatSing(head);
30 //find median
31 double result = findMedian(head);
32 //print the median
33 cout<<" median = "<<result<<endl;
34 cout<<endl<<" ---------- Luxuriant line ---------- "<<endl<<endl;
35 head = NULL;
36 }
37
38 return 0;
39 }
40
41 /* ---the key function--- */
42 double findMedian(Node *head)
43 {
44 Node *fast; //fast pointer, 2 steps/time
45 Node *slow; //slow pointer, 1 step/time
46 fast = slow = head; //start at head
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
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<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;
80 q = head;
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 }运行输出结果：
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-07-20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读