快慢指针

一、快慢指针说明

  快慢是指移动步数的长短,也就是每次向前移动速度的快慢。如,指定快指针每次沿着链表向前移动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 }

  运行输出结果:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

扫码关注云+社区