快慢指针

一、快慢指针说明

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

相关文章

来自专栏闻道于事

Java 集合补充

集合和数组不一样,数组元素可以是基本类型的值,也可以是对象(的引用变量),集合里只能保存对象(的引用变量)。

1265
来自专栏灯塔大数据

塔秘 | 从Zero到Hero,一文掌握Python关键代码

前 言 本文整体梳理了 Python 的基本语法与使用方法,并重点介绍了对机器学习十分重要且常见的语法,如基本的条件、循环语句,基本的列表和字典等数据结构,此...

3478
来自专栏BestSDK

封装、私有,一文掌握Python关键代码

首先,什么是 Python?根据 Python 创建者 Guido van Rossum 所言,Python 是一种高级编程语言,其设计的核心理念是代码的易读性...

3853
来自专栏java技术学习之道

java集合类详解

1486
来自专栏数据科学学习手札

(数据科学学习手札49)Scala中的模式匹配

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

1004
来自专栏C/C++基础

C++虚拟继承与虚基类

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

762
来自专栏Android机动车

数据结构学习笔记——串

枯眼望遥山隔水, 往来曾见几心知? 壶空怕酌一杯酒, 笔下难成和韵诗。 途路阻人离别久, 讯音无雁寄回迟。 孤灯夜守长寥寂, 夫忆妻兮父忆儿。

793
来自专栏WindCoder

JavaScript字符串数组排序

思考路线:需要区分数字字符和非数字字符,故可知数字字符为此条件中的”特殊字符“,即特殊情况,需单独处理。数字字符的ASCII值为48-57。每次比较两个字符串(...

2141
来自专栏前端黑板报

一个数字截取引发的精度问题(三)

上次总结的第四条: 当传入的参数小于数字的整数位时,返回指数形式表示的字符串。 let numObj = 12345.6numObj.toPrecision(2...

2078
来自专栏Java帮帮-微信公众号-技术文章全总结

第十七天 集合-Collection&amp;增强for&amp;迭代器【悟空教程】

出现意义:面向对象语言对事物的体现都是以对象的形式,所以为了方便对多个对象的操作,就对对象进行存储,集合就是存储对象最常用的一种方式。

1132

扫码关注云+社区

领取腾讯云代金券