手机版
你好,游客 登录 注册
背景:
阅读新闻

链表是否有环的两种判断方法

[日期:2017-06-24] 来源:cnblogs.com/AsuraDong  作者:AsuraDong [字体: ]

判断单链表是否有环

假设有一个含环链表:1-2-3-4-5-6-3(6又连接到3,形成一个环)

 

  1. 使用p、q两个指针,p总是向前走,但q每次都从头开始走,对于每个节点,看p走的步数是否和q一样。当p从6走到3时,用了6步;此时q从head出发,则只需两步就到3,因而步数不等,出现矛盾,存在环。而且可以锁定环的位置,就是q的步数+1

  2. 使用p、q两个指针,p每次向前走一步,q每次向前走两步,若在某个时候p == q,则存在环。虽然无法锁定环的位置,但是占用空间和时间少。这就是之前说的快慢链表里面的快慢指针。

实现:

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXLEN = 6;

struct Node{
    int val;
    Node *next;
};


int  IfLoop(Node *head){
    Node * cur1 = head;
    int pos1 = 0;
    while(cur1){
        Node * cur2 = head;
        int pos2 = 0;
        pos1++;
        while(cur2){
            pos2++;
            if(cur2==cur1){
                if(pos1==pos2)
                    break;
                else
                    return pos2;
            }
            cur2 = cur2->next;
        }
        cur1 = cur1->next;
    }
    return -1;
}

bool IfLoop_2(Node *head){
    Node * p = head;
    Node * q = head;
    while(p && q){
        p = p->next;
        q = q->next;
        if(q)
            q = q->next;
        if (p && p==q)
            return true;
    }
    return false;
}

int main(){
    Node *head = new Node;
    head->val = 0;
    
    Node *s = new Node; 
    
    Node *p = new Node;
    head->next = p;
    
    for(int i=0;i<MAXLEN;++i){
        p->val = i+1;
        p->next = s; 
        p =s;
        s = new Node;
    }
    
    p->next = head->next->next;
     
    cout<<"位置在:"<<IfLoop(head)<<",如果位置是-1,则不存在"<<endl;
        
    return 0;
    
}

本文永久更新链接地址http://www.linuxidc.com/Linux/2017-06/145147.htm

linux
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款