精华内容
下载资源
问答
  • C++快慢指针理解与应用原理应用有序链表中寻找中位数判断链表是否存在环,如果存在,找到环入口判断两个单链表是否相交,如果相交找到他们的第一个公共节点 原理 快慢指针中的快慢指的是移动的步长,即每次向前移动...

    原理

    快慢指针中的快慢指的是移动的步长,即每次向前移动的快慢,例如每次可以让快指针沿链表向前移动2,慢指针向前移动1次。

    应用

    有序链表中寻找中位数

      快指针移动的速度是慢指针移动速度的两倍,因此当快指针到达链表尾部的时候,慢指针刚好到达中点。
      程序还要考虑链表节点个数的奇偶数因数,当快指针移动x次后到链表尾1+2x1+2x,说明链表有奇数个节点,直接返回慢指针指向的数据即可。
      如果快指针是倒数第二个结点,说明链表结点个数是偶数,这时可以根据“规则”返回上中位数或下中位数或(上中位数+下中位数)的一半。

    while(fast && slow){
    	if(fast->next == NULL){
    		return slow->data;
    	}else if(fast->next != NULL && fast->next->next == NULL){
    		return (slow->data + slow->next->data)/2;
    	}else{
    		fast = fast->next->next;
    		slow = slow->next;
    	}
    }
    

    判断链表是否存在环,如果存在,找到环入口

      有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表尾部形成一个环。
      如果判断一个链表是否存在一个环?设定两个指针slow,fast,均从头指针开始,每次分别前进1步、2步。如果存在环,则两者相遇;如不存在环,fast遇到NULL退出。
      如果链表存在环,如果找到环的入口点?当fast与slow相遇时,slow肯定没有遍历完链表或者恰好遍历一遍。于是我们从链表头与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,则相遇的第一个点为环入口点。

    node* findLoopPort(node *head) {
    	node *fast;
    	node *slow;
    	while (fast && fast->next) {	
    		//第一步:判断链表是否存在环
    		slow = slow->next;
    		fast = fast->next->next;
    		if (slow == fast) {
    			break;
    		}
    	}
    	if ((fast == NULL) || (fast ->next == NULL)) {	//链表不存在环
    		return NULL;
    	}
    	//第二步:寻找环的入口点
    	slow = head;	//让slow回到链表的起点,fast留在相遇点
    	while (slow != fast) {	//当slow和fast再次相遇,那个点就是环的入口点
    		slow = slow->next;
    		fast = fast->next;
    	}
    	reurn slow;
    }
    

    判断两个单链表是否相交,如果相交找到他们的第一个公共节点

      判断两个链表是否相交,如果相交,给出相交的第一个点(假设两个链表不存在环)。
    思路:
      首先利用快慢指针判断链表是否存在环。
      (a)如果不存在环,则如果两个单向链表有公共节点,也就是两个链表从某一节点开始,他们的p_next都指向同一个节点,每一个节点只有一个p_next。因此从第一个公共节点开始,之后他们所有节点都是重合的。因此,首先两个链表先遍历一次,求两个链表的长度分别是L1、L2,然后可以得到他们的长度差L。然后先在长的链表上遍历L个节点,之后再同步遍历,于是在遍历中,第一个相同节点就是第一个公共节点。此时,若两个链表长度分别是M、N,则时间复杂度为O(M+N)。

    • 如果两个指针没有环且相交于一个节点,这个节点后面都是共有的。所以如果两个链表相交,那么两个链表的结尾节点的地址也是一样的。程序实现时分别遍历两个单链表,直到尾结点。判断尾结点地址是否相等即可。时间复杂度为O(L1+L2)。
    • 如果找到第一个相交的节点?判断是否相交的时候,记录两个链表的长度,算出长度差len,接着先让较长的链表遍历len个长度,然后两个链表同时遍历,判断是否相等,如果相等,就是第一个相交的节点。
    void Is_2List_Intersect(LinkList L1, LinkList L2){
    	if (L1 == NULL || L2 == NULL) {
    		exit(ERROR);
    	}
    	LinkList p = L1;
    	LinkList q = L2;
    	int L1_length = 0;
    	int L2_length = 0;
    	int len = 0;
    
    	while (p->next) {
    		L1_length++;
    		p = p->next;
    	}
    	while (q->next) {
    		L2_length++;
    		q = q->next;
    	}
    
    	printf("p: = %d\n", p);
        printf("q: = %d\n", q);
     
        printf("L1_length: = %d\n", L1_length);
        printf("L2_length: = %d\n", L2_length);
    
    	if (p ==q) {
    		printf(" 相交\n")
    		/*p重新指向短的链表 q指向长链表*/
    		if (L1_length > L2_length) {
    			len = L1_length - L2_length;
    			p = L2;
    			q = L1;
    		} else {
    			len = L2_length - L1_length;
    			p = L1;
    			q = L2;
    		}
    	
    		while (len) {
    			q = q->next;
    			len--;
    		}
    		while (p != q) {
    			p = p->next;
    			q = q->next;	
    		}
    		printf("相交的第一个结点是:%d\n",p->data);
    	} else {
    		printf("不相交\n");
    	}
    }
    

      (b)如果一个存在环,另一个不存在环,则这两个链表是不可能相交的。
      (c)如果利用快慢指针发现两个链表都存在环,则判断任意一个链表上快慢指针相遇的那个节点,在不在另外一个链表上,如果在,则相交,不在,则不相交。

    展开全文
  • C++快慢指针的应用

    2019-09-10 10:40:52
    快慢指针 快慢指针中的快慢指的是移动的步长,即每次向前移动的快慢,例如每次可以让快指针沿链表向前移动2,慢指针向前移动1次。 快慢指针的应用 (1)判断单链表是否存在环   如果链表是一个环,就好像...

    快慢指针

    • 快慢指针中的快慢指的是移动的步长,即每次向前移动的快慢,例如每次可以让快指针沿链表向前移动2,慢指针向前移动1次。

    快慢指针的应用

    (1)判断单链表是否存在环
      如果链表是一个环,就好像操场的跑道是一个环一样,此时快慢指针都从链表头开始遍历,快指针每次向前移动两个位置,慢指针每次向前移动一个位置;如果快指针到达NULL,说明链表以NULL为结尾,没有环。如果快指针追上慢指针,则表示有环。代码如下:

    bool HasCircle(Node *head){
    	if(head == NULL)
    		return false;
    	Node *slow = head;
    	Node *fast = head;
    	while(fast != NULL && fast->next != NULL){
    		slow = slow->next;	//慢指针每次前进一步
    		fast = fast->next->next;	//快指针每次前进两步
    		if(slow == fast){		//相遇,存在环
    			return true;	
    		}
    		return false;
    	}
    }	
    

    (2)在有序链表中寻找中位数
      慢指针移动的速度是快指针移动速度的两倍,因此当快指针到达链表尾部的时候,慢指针刚好到达中点。
      程序还要考虑链表节点个数的奇偶数因数,当快指针移动x次后到链表尾(1+2x),说明链表有奇数个节点,直接返回慢指针指向的数据即可。
      如果快指针是倒数第二个结点,说明链表结点个数是偶数,这时可以根据“规则”返回上中位数或下中位数或(上中位数+下中位数)的一半。

    while(fast && slow){
    	if(fast->next == NULL){
    		return slow->data;
    	}else if(fast->next != NULL && fast->next->next == NULL){
    		return (slow->data + slow->mext->data)/2;
    	}else{
    		fast = fast->next->next;
    		slow = slow->next;
    	}
    }
    

    (3)判断链表是否存在环,如果存在,找到环入口
      有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表尾部形成一个环。
      如果判断一个链表是否存在一个环?设定两个指针slow,fast,均从头指针开始,每次分别前进1步、2步。如果存在环,则两者相遇;如不存在环,fast遇到NULL退出。
      如果链表存在环,如果找到环的入口点?当fast与slow相遇时,slow肯定没有走遍历完链表或者恰好遍历一遍。于是我们从链表头与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,则相依的第一个点为环入口点。

    node* findLoopPort(node *head){
    	node *fast;
    	node *slow;
    	while(fast && fast->next){	
    //第一步:判断链表是否存在环
    			slow = slow->next;
    			fast = fast->next->next;
    			if(slow == fast){	//链表不存在
    				break;
    			}
    	}
    	if((fast == NULL) || (fast ->next == NULL)){	//链表不存在
    		return NULL;
    	}
    //第二步:寻找环的入口点
    	slow = head;	//让slow回到链表的起点,fast留在相遇点
    	while (slow != fast){	//当slow和fast再次相遇,那个点就是环的入口点
    		slow = slow->next;
    		fast = fast->next;
    	}
    	reurn slow;
    }
    

    (4)判断两个单链表是否相交,如果相交找到他们的第一个公共节点
      判断两个链表是否相交,如果相交,给出相交的第一个点(假设两个链表不存在环)。
    思路
      首先利用快慢指针判断链表是否存在环。
      (a)如果不存在环,则如果两个单向链表有公共节点,也就是两个链表从某一节点开始,他们的p_next都指向同一个节点,每一个节点只有一个p_next。因此从第一个公共节点开始,之后他们所有节点都是重合的。因此,首先两个链表先遍历一次,求两个链表的长度分别是L1、L2,然后可以得到他们的长度差L。然后先在长的链表上遍历L个节点,之后再同步遍历,于是在遍历中,第一个相同节点就是第一个公共节点。此时,若两个链表长度分别是M、N,则时间复杂度为O(M+N)。

    • 如果两个指针没有环且相交于一个节点,这个节点后面都是共有的。所以如果两个链表相交,那么两个链表的结尾节点的地址也是一样的。程序实现时分别遍历两个单链表,直到尾结点。判断尾结点地址是否相等即可。时间复杂度为O(L2+L2)。
    • 如果找到第一个相交的节点?判断是否相交的时候,记录两个链表的长度,算出长度差len,接着先让较长的链表遍历len个长度,然后两个链表同时遍历,判断是否相等,如果相等,就是第一个相交的节点。
    void Is_2List_Intersect(LinkList L1, LinkList L2){
    	if(L1 == NULL || L2 == NULL){
    		exit(ERROR);
    	}
    	LinkList p = L1;
    	LinkList q = L2;
    	int L1_length = 0;
    	int L2_length = 0;
    	int len = 0;
    
    	while(p->next){
    		L1_length++;
    		p = p->next;
    	}
    	while(q->next){
    		L2_length++;
    		q = q->next;
    	}
    
    	printf("p: = %d\n", p);
        printf("q: = %d\n", q);
     
        printf("L1_length: = %d\n", L1_length);
        printf("L2_length: = %d\n", L2_length);
    
    	if(p ==q){
    		printf(" 相交\n")
    		/*p重新指向短的链表 q指向长链表*/
    		if(L1_length > L2_length){
    			len = L1_length - L2_length;
    			p = L2;
    			q = L1;
    		}else{
    			len = L2_length - L1_length;
    			p = L1;
    			q = L2;
    		}
    	
    		while(len){
    			q = q->next;
    			len--;
    		}
    		while(p != q){
    			p = p->next;
    			q = q->next;	
    		}
    		printf("相交的第一个结点是:%d\n",p->data);
    	}else{
    		printf("不相交\n");
    	}
    }
    

      (b)如果一个存在环,另一个不存在环,则这两个链表是不可能相交的。
      (c)如果利用快慢指针发现两个链表都存在环,则判断任意一个链表上快慢指针相遇的那个节点,在不在另外一个节点上,如果在,则相交,不在,则不相交。

    展开全文
  • 快慢指针求ListNode的中点,网上的答案大都是下面这个: struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: ListNode* middleNode...

    用快慢指针求ListNode的中点,网上的答案大都是下面这个:

    struct ListNode {
          int val;
          ListNode *next;
          ListNode(int x) : val(x), next(NULL) {}
     };
    class Solution {
    public:
        ListNode* middleNode(ListNode* head) {
            ListNode* slow = head;
            ListNode* fast = head;
            while (fast != NULL && fast->next != NULL) {
                slow = slow->next;
                fast = fast->next->next;
            }
            return slow;
        }
    };

    但是实际运行时会报bug,原因在于循环的判断条件,如果fast==NULL,那么利用NULL指针访问next(第二个条件)必然会报错,基于此,做如下修改:

    struct ListNode {
          int val;
          ListNode *next;
          ListNode(int x) : val(x), next(NULL) {}
     };
    
    class Solution {
    public:
        ListNode* middleNode(ListNode* head) {
            if(head==NULL){
                return head;
            }
            if(head->next==NULL){
                return head;
            }
            ListNode *slow=head;
            ListNode *fast=head;
            while(fast!=NULL){
                if(fast->next==NULL){
                    break;
                }
                slow=slow->next;
                fast=fast->next->next;
            }
            return slow;
        }
    };

    在利用快慢指针判断链表中有没有环的题目中,也需要这样的判断,因为如果把两个判断条件写在一起,在第一个不满足的情况下,第二个会出现访问的问题。

    最近又重新考虑了这个问题,发现原始代码应该是没错的,因为  && 连接的两个判断条件,当第一个条件不满足时不会再考虑第二个条件,因此也就不存在上述的问题。。。。。。

     

    展开全文
  • 在Discuss里看到了一种快慢指针解法,觉得太太太巧妙了! 设两个指针,同时出发,但一个指针每次走两步,一个指针每次走一步,若存在环,则两个指针经过一定步数 之后必定会相遇,快慢指针只需o(1)的空间复杂度。 ...

    Problem

    题目链接

    Solution

    题意为,给你一个链表,这个链表的尾节点的next可能连接到了之前的某个节点,就形成了一个环,请你判断

    所给的链表是否含有环。

    我自己的做法就很暴力,开了set,边遍历边存下指针,判断是否有之前出现过的指针重复出现,若重复出现则

    必定存在环。

    在Discuss里看到了一种快慢指针解法,觉得太太太巧妙了!

    设两个指针,同时出发,但一个指针每次走两步,一个指针每次走一步,若存在环,则两个指针经过一定步数

    之后必定会相遇,快慢指针只需o(1)的空间复杂度。

    class Solution {
    public:
        bool hasCycle(ListNode *head) {
            if(head==nullptr) return false;
            
            ListNode* p=head->next;
            ListNode* q=head->next;
            
            while(q&&q->next){
                p=p->next;
                q=q->next->next;
                if(p==q) return true;
            }
            
            return false;
        }
    };
    
    展开全文
  • 思路就是利用快慢指针,快指针每次走两步,慢指针每次走一步,当快指针抵达链表尾部的时候,慢指针到达链表中间,需要注意的是,因为回文串是正读泛读都一样的字符串,因此慢指针移动时,我们需要把链表前半部分的...
  • 简要概述快慢指针法(单向链表): 设置两个指针,初始值均为头节点。 快指针为一次前进两个节点。慢指针为一次前进一个节点。快指针走到头的时候慢指针应该恰好到中点位置,慢指针在前进过程中顺便将链表反向链接。...
  • 1.设置fast,slow两个指针指向链表头结点 2.fast每次走两步,slow每次走一步 3.当fast为空或fast->next为空时结束循环 4.此时slow指向的结点就是链表的中间结点 T getmid() { Node* fast = head; Node* slow = ...
  • 这里发现了一个很有意思的思路,即快慢指针 假设有快慢两个运动员,快的运动员一次跑两步,慢的运动员一次跑一步,如果跑道是圆环的,那么第二圈的时候一定会相遇,如果是直线的就不会相遇。以两个运动员是否相遇...
  • 快慢指针注意几点: 1.在调用next字段前,始终检查节点是否为空。 获取空节点的下一个节点将导致空指针错误。例如:fast=fast->next->next之前,需要检查fast和fast->next不为空。 2.仔细定义循环的结束...
  • 给定一个包含 n + 1 个整数的数组 nums ,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。 假设 nums 只有 一个重复的整数 ,找出 这个...基本上将这里面的题解浏览了一遍,发现快慢指针这种解法
  • 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环...
  • 方法一:快慢指针,时间O(N),空间O(1) 快指针=2倍速的慢指针,反转链表,直到快指针达到尾节点,慢指针达到中间节点,停止反转。 将反转后的链表(链表前半部分)和链表后半部分进行比较,若数值相同则为回文链表 若...
  • 快慢指针 思路与算法 我们使用两个指针,fast 与 slow。它们起始都位于链表的头部。随后,slow 指针每次向后移动一个位置,而 fast 指针向后移动两个位置。如果链表中存在环,则 \fast 指针最终将再次与 slow 指针...
  • 快慢指针

    2017-03-08 11:20:35
    快慢指针  快慢指的是移动的步长,即每次向前移动速度的快慢。一般规定为快指针每次沿链表向前移动2,慢指针每次向前移动1次。 快慢指针应用 1.判断单链表是否为循环链表。 2.寻找链表的中间位置。 3.如果链表有...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,375
精华内容 1,350
关键字:

c++快慢指针

c++ 订阅