《信息学C++知识讲解》:双指针的使用总结(一)

《信息学C++知识讲解》:双指针的使用总结(一)

双指针是一种解决问题的技巧或者思维方式,指在访问一个序列中的数据时使用两个指针进行扫描,两个指针可以是同向的,也可以是反向的;我们的关注点可以是这两个指针指向的两个元素本身,也可以是两个指针中间的区域。

快慢指针

01、快慢指针的概念
快慢指针是两个指针同向移动,某一时刻来看两个指针一个在前,一个在后,即快指针和慢指针。造成两个指针一前一后的原因有两种情况:

①.两个指针速度相同,但是出发时间不同,也可以认为是出发起始位置不同,在两个指针都出发后会以固定的距离间隔一前一后的向前移动;

②.两个指针速度不同,但是从同一个起点同时出发,之后会以固定的速度差一前一后的向前移动,两个指针的距离间隔随时间规律的递增;

02、应用示例-链表中倒数第k个节点

输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。示例:给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5.

力扣(LeetCode)面试题22

访问链表的节点只能从前往后进行节点的遍历。对应本题一般解法可以先从头到尾进行一趟遍历得到链表长度 length ,然后再从头开始进行一趟 遍历,但是只遍历 length – k 个节点即可。

利用双指针可以只进行一次遍历即可,两个指针都从头节点出发,让快指针先走 k 步,然后慢指针再出发,两个指针以相同的速度前进,则两个 指针间的距离始终为 k ,所以当快指针刚好走过链接尾节点时,慢指针刚好到达倒数第 k 个节点的位置。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode* getKthFromEnd(ListNode* head, int k) {        ListNode *fast = head, *slow = head; //初始化        while(k--) {   //让false指针先走K步            fast = fast->next;        }        while(fast != nullptr) {//两个指针以相同的步长同时移动,直到 fast == nullptr            fast = fast->next;            slow = slow->next;        }        return slow;//slow刚好为倒数第k的位置    }};

03、应用示例-链表的中间结点

给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。示例 1:输入:[1,2,3,4,5] 输出:此列表中的结点 3 (序列化形式:[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。注意,我们返回了一个 ListNode 类型的对象 ans,这样:ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL

力扣(LeetCode)第876题

访问链表的节点只能从前往后进行节点的遍历。对应本题一般解法可以先从头到尾进行一趟遍历得到链表长度 length ,然后再从头开始进行一趟 遍历,遍历到第 N/2 个元素即可。

同样,利用双指针可以只进行一次遍历即可,两个指针同时从头节点结点出发,快指针每次走两步,慢指针走一步,则相同的时间内快指针前进 的距离始终是慢指针的两倍,所以当快指针刚好走过链接尾结点时,慢指针刚好到达链表的中间结点位置。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode* middleNode(ListNode* head) {        ListNode * fast= head, * slow = head;//初始化        while(fast != NULL && fast->next !=NULL)        {            slow = slow->next;//慢指针走一步            fast = fast->next;//快指针走两步            fast = fast->next;                    }        return slow;    }};

04、应用示例-环形链表

给定一个链表,判断链表中是否有环。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。示例 1:输入:head = [3,2,0,-4], pos = 1 输出:true 解释:链表中有一个环,其尾部连接到第二个节点。

力扣(LeetCode)第141题

我们对链表从头结点开始进行遍历,若链表中存在环,则环内的结点会重复一直遍历,不存在环或者环外的结点只会遍历一次;因此我们用一个 set 来存储已经遍历过的结点,当遍历到一个结点时查找 set中是否存在,若已经存在则一定存在环。

也可以使用双指针来解答本题,两个指针同时从头节点结点出发,快指针每次走两步,慢指针走一步,则单位时间内快指针相对慢指针移动距离的增量为 1 ,即经过相同的时间 k ,快指针比慢指针多走了 k 步;当两个指针都进入环中时,假设规定慢指针在前、快指针在后,即快指针追赶慢指针,因为单位时间内快指针可以把距离缩短 1 步,因此随着时间的推移快指针肯定会追赶上慢指针。若不存在环,则快指针和慢指针不会在链表中的某个结点相遇。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    bool hasCycle(ListNode *head) {     ListNode * fast= head,* slow = head;//初始化       while(fast != NULL && fast->next !=NULL)       {            slow = slow->next;//慢指针走一步            fast = fast->next;//快指针走两步            fast = fast->next;            if( fast == slow)//两者相遇则有环                return true;          }       return false;    }};
叮当学习力:数理逻辑思维课
点图或扫码领0元课
叮当学习力-逻辑思维
更多课程

 

微信扫码领取0元编程课


核桃编程-弹窗图

This will close in 180 seconds

少儿编程0元课

 
少儿编程0元课  

少儿0元课导航

 
少儿0元课导航  

少儿逻辑0元课

 
少儿逻辑0元课  

公众号

关注公众号

x
少儿编程学习网
专注青少年编程学习、课程推荐、科技特长生规划
2023-01-27 06:30:46
您好,有任何疑问请与我们联系!
您的工单我们已经收到,我们将会尽快跟您联系!
[官方群:675726029]
[Mars老师:Qbit-School]
[Mars老师]
17732463686
取消

选择聊天工具: