精华内容
下载资源
问答
  • /*判断两个链表是否交叉,如果交叉返回交叉节点,否则返回NULL。*/ Node* findCross(Node* head1,Node* head2) { if(head1==NULL||head2==NULL) return NULL; /*将第二个链表变成环链*/ Node* tail2=...
    /*判断两个链表是否交叉,如果交叉返回交叉节点,否则返回NULL。*/  
    Node* findCross(Node* head1,Node* head2)  
    {  
        if(head1==NULL||head2==NULL)  
            return NULL;  
        /*将第二个链表变成有环链表*/  
        Node* tail2=head2;  
        while(tail2->next!=NULL)  
            tail2=tail2->next;  
        tail2->next = head2;        
        Node* temp = findCircle(head1);  
        if(temp!=NULL)  
            return temp;  
        else  
            return NULL;          
    }  
    分析:
    如果两个链表有交点,则把第一个链表的尾节点的next域指向第二个链表的首结点会构成一个环,然后判断是否有环即可,有环说明有交点,无环说明无交点

    展开全文
  • 如何判断两个链表是否有交点 首先,两个链表如果有交点它应该是y型的。 分别遍历两个链表,如果尾节点地址相同,则有交点 分别遍历两个链表,计算两链表长度,长的为A,短的为B,让长的链表先走A-B步,然后两个...

    如何判断两个链表是否有交点

    首先,两个链表如果有交点它应该是y型的。

    1. 分别遍历两个链表,如果尾节点地址相同,则有交点
    2. 分别遍历两个链表,计算两链表长度,长的为A,短的为B,让长的链表先走A-B步,然后两个链表仪器走,走到同一地址处为交点。
    3. 把两个链表压到两个栈里,分别将栈顶弹出,比较,知道弹出的地址不同,则上一个弹出的为交点。
    4. 把两个链表放到两个数组中遍历,地址相同为交点。

     

    1. 如何判断单向链表是否有环
    1. 遍历放到链表中,直到重复点出现,即为入口点。
    2. 2个指针,一个一次走一步,一个一次走两步,相遇则有环,从相遇点断开,变为Y型,入口点即为相交点。
    3. 计算环的长度,两个指针p1和p2,p1先走x步,然后两个指针一起走,相遇点为入口点。
    展开全文
  •  如果存在交点两个链表交点及其之后的部分是一致的-----这点很关键,一致的意思包括两部分:长度和内容。 struct Node { int data; struct Node * next; }; Node* FixIntersetion(Node* ...

    解题思路:

             如果存在交点,两个链表在交点及其之后的部分是一致的-----这点很关键,一致的意思包括两部分:长度和容。


    1. struct Node  
    2. {  
    3.     int data;  
    4.     struct Node * next;  
    5. };  
    6.   
    7.  Node* FixIntersetion(Node* pHead1, Node* pHead2)  
    8. {  
    9.     Node* p1 = pHead1;  
    10.     Node* p2 = pHead2;  
    11.     int i = 1, j = 1, k = 0, diff = 0;  
    12.     //如果都是空链表,肯定没有交点  
    13.     if(pHead2 == NULL || pHead2 == NULL)  
    14.     {  
    15.         return NULL;  
    16.     }  
    17.     //获取链表长度  
    18.     while(p1->next != NULL)  
    19.     {  
    20.         p1 = p1->next;  
    21.         i++;  
    22.     }  
    23.     while(p2->next != NULL)  
    24.     {  
    25.         p2 = p2->next;  
    26.         j++;  
    27.     }  
    28.     //开始判断是否存在交点  
    29.     if(p1 != p2)  
    30.     {//根据有交点时,两个链表在交点及其之后的部分是公共的,因此,有交点的单链表的尾节点必定相同  
    31.         return NULL;        //如果尾节点不同,直接返回NULL  
    32.     }  
    33.     else                   //否则寻找第一个相同的节点  
    34.     {  
    35.         p1=pHead1;  
    36.         p2=pHead2;  
    37.         //使得两者的起始比较位置离尾部的长度一致  
    38.         if(i>j)  
    39.         {  
    40.             diff=i-j;   
    41.             for(k=0; k<diff; k++)  
    42.             {  
    43.                 p1 = p1->next;  
    44.             }  
    45.         }  
    46.         if(i<j)  
    47.         {  
    48.             diff=j-i;   
    49.             for(k=0; k<diff; k++)  
    50.             {  
    51.                 p2 = p2->next;  
    52.             }  
    53.         }  
    54.         //开始比对,得出交点  
    55.         while(p1 != p2)  
    56.         {  
    57.             p1 = p1->next;  
    58.             p2 = p2->next;  
    59.         }  
    60.         return p1;  
    61.     }  



    展开全文
  • 原文;... 题目:给两个单链表,如何判断两个单链表是否相交?若相交,则找出第一个相交的节点。...因为两个链表一个共同节点,则这个节点里的指针域指向的下一个节点地址一样,所以下一个节点也会相交,依次

    原文;https://blog.csdn.net/fengxinlinux/article/details/78885764

    题目:给两个单链表,如何判断两个单链表是否相交?若相交,则找出第一个相交的节点。
    这道题的思路和解法有很多,在这把这道题的解法做一个详细的总结。


    解这道题之前,我们需要首先明确一个概念:
    如果两个单链表有共同的节点,那么从第一个共同节点开始,后面的节点都会重叠,直到链表结束。
    因为两个链表中有一个共同节点,则这个节点里的指针域指向的下一个节点地址一样,所以下一个节点也会相交,依次类推。所以,若相交,则两个链表呈“Y”字形。如下图:

    这里写图片描述

    1.暴力解法。
    从头开始遍历第一个链表,遍历第一个链表的每个节点时,同时从头到尾遍历第二个链表,看是否有相同的节点,第一次找到相同的节点即第一个交点。若第一个链表遍历结束后,还未找到相同的节点,即不存在交点。时间复杂度为O(n^2)。这种方法显然不是写这篇博客的重点。。。不多说了。

    2.使用栈。
    我们可以从头遍历两个链表。创建两个栈,第一个栈存储第一个链表的节点,第二个栈存储第二个链表的节点。每遍历到一个节点时,就将该节点入栈。两个链表都入栈结束后。则通过top判断栈顶的节点是否相等即可判断两个单链表是否相交。因为我们知道,若两个链表相交,则从第一个相交节点开始,后面的节点都相交
    若两链表相交,则循环出栈,直到遇到两个出栈的节点不相同,则这个节点的后一个节点就是第一个相交的节点。

    node temp=NULL;  //存第一个相交节点
    
    while(!stack1.empty()&&!stack1.empty())  //两栈不为空
    {
        temp=stack1.top();  
        stack1.pop();
        stack2.pop();
        if(stack1.top()!=stack2.top())
        {
            break;
        }
    }
    
    

    这个方法在没有要求空间复杂度的时候,使用栈来解决这个问题也是挺简便的。

    3.遍历链表记录长度。
    同时遍历两个链表到尾部,同时记录两个链表的长度。若两个链表最后的一个节点相同,则两个链表相交。

    有两个链表的长度后,我们就可以知道哪个链表长,设较长的链表长度为len1,短的链表长度为len2。
    则先让较长的链表向后移动(len1-len2)个长度。然后开始从当前位置同时遍历两个链表,当遍历到的链表的节点相同时,则这个节点就是第一个相交的节点。
    这里写图片描述

    代码示例:

    typedef struct node_t
    {
        int data;//data
        struct node_t *next; //next
    }node;
    
    node* find_node(node *head1, node *head2)
    {
        //链表带头节点
        if(head1==NULL || head2==NULL)
        {
            return NULL;//如果有为空的链表,肯定是不相交的
        }
        node *p1, *p2;
        p1 = head1;
        p2 = head2;
        int len1 = 0;
        int len2 =0;
        int diff = 0;
        while(p1->next!=NULL)
        {
            p1 = p1->next;
            len1++;
        }
        while(p2->next!=NULL)
        {
            p2 = p2->next;
            len2++;
        }
        if(p1 != p2) //如果最后一个节点不相同,返回NULL
        {
            return NULL;
        }
        diff = abs(len1 - len2);
        if(len1 > len2)
        {
            p1 = head1;
            p2 = head2;
        }
        else
        {
            p1 = head2;
            p2 = head1;
        }
        for(int i=0; i<diff; i++)
        {
            p1 = p1->next;
        }
        while(p1 != p2)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }
    

     

    这个方法也非常的简便并且额外的空间开销很小。时间复杂度为O(len1+len2)。

    4.哈希表法。

    既然连个链表一旦相交,相交节点一定有相同的内存地址,而不同的节点内存地址一定是不同的,那么不妨利用内存地址建立哈希表,如此通过判断两个链表中是否存在内存地址相同的节点判断两个链表是否相交。具体做法是:遍历第一个链表,并利用地址建立哈希表,遍历第二个链表,看看地址哈希值是否和第一个表中的节点地址值有相同即可判断两个链表是否相交。
    我们可以采用除留取余法构造哈希函数。
    构造哈希表可以采用链地址法解决冲突。哈希表冲突指对key1 != key2,存在f(key1)=f(key2),链地址法就是把key1和key2作为节点放在同一个单链表中,这种表称为同义词子表,在哈希表中只存储同义词子表的头指针,如下图:

    这里写图片描述

    示例代码就不列举了,感兴趣的可以自己写写。

    时间复杂度O(length1 + length2)。

     

    5.问题转化为判断一个链表是否有环问题。

    这个问题我们可以转换为另一个等价问题:如何判断一个单链表是否有环,若有环,找出环的入口?
    如何转化?
    先遍历第一个链表到它的尾部,然后将尾部的next指针指向第二个链表(尾部指针的next本来指向的是null)。这样两个链表就合成了一个链表。若该链表有环,则原两个链表一定相交。否则,不相交。
    这样进行转换后就可以从链表头部进行判断了,其实并不用。通过简单的了解我们就很容易知道,如果新链表是有环的,那么原来第二个链表的头部一定在环上。因此我们就可以从第二个链表的头部进行遍历的,从而减少了时间复杂度(减少的时间复杂度是第一个链表的长度)。
    看了下面的示例图就明白了:

    这里写图片描述

    知道了转化的方法后,那么重点的问题来了。我们如何判断一个链表是否有环,如何找到环的入口?
    判断是否有环,我们一般容易想到的方法就是记录每个节点是否被访问过,若一个节点被访问了两次,则该链表一定有环。

    其实来有一个更为巧妙的方法!

    (1)判断链表是否存在环


    设置两个链表指针fast, slow,初始值都指向链表头结点,然后两个指针都往后走,不同的是slow每次前进一步,即前进一个节点。fast每次前进两步,如果存在环,两个指针必定相遇。
    因为只有存在环的情况,我们才可能出现走的快的指针能再次遇到慢的指针。
    并且还有一点就是,若该链表存在环,则在慢指针还没走完一整个环的路程之前,两指针已经相遇。
    为什么?因为从慢指针进入环入口开始计时,慢指针走完一圈的时间,此时快指针已经走了两圈。所以在慢指针走完一圈之前,两指针一定会相遇。

    (2)若链表有环,找到环的入口点
    由(1)我们可以知道,当fast与slow相遇时,slow还没走完链表,而fast已经在环内循环了n圈了。
    如图:
    这里写图片描述

    我们把两指针相遇点记为O。则慢指针已走的环路程记为x,环剩下的路程记为y。
    设slow在相遇前走了s步,则fast走了2s步,设环长为r,有2s=s+nr,即s=nr。

    由上图可知a+x=s, x+y=r,而我们的目标是找到a的位置。a+x=s=nr=(n-1)r+r=(n-1)r+y+x,则a=(n-1)r+y. 这个公式告诉我们,从链表头和相遇点O分别设一个指针,每次各走一步,这两个指针必定相遇,且相遇的第一个点为环入口点。

    示例代码如下:

    struct Link  
    {  
        int data;  
        Link *next;  
    };  
    
    // 插入节点  
    void insertNode(Link *&head, int data)  
    {  
        Link *node = new Link;  
        node->data = data;  
        node->next = head;  
        head = node;  
    }  
    
    // 判断链表是否存在环  
    Link* hasCycle(Link* head)  
    {  
        Link *fast, *slow;  
        slow = fast = head;  
        while (fast && fast->next)  
        {  
            fast = fast->next->next;  
            slow = slow->next;  
            if (fast == slow)  
                return slow;  
        }  
        return NULL;  
    }  
    
    // 确定环的入口点,pos表示fast与slow相遇的位置  
    Link* findCycleEntry(Link* head, Link* pos)  
    {  
        while (head != pos)  
        {  
            head = head->next;  
            pos = pos->next;  
        }  
        return head;  
    }  

     

    扩展问题:如何判断两个存在环的单链表是否相交?如何找出第一个交点?

    通过方法(1)我们能够分别找出两个链表的相遇点pos1, pos2,然后还是使用两个指针fast和slow,都初始化为pos1,且fast每次前进2步,slow每次前进1步。若fast指针在遇到slow前,出现fast等于pos2或fast->next等于pos2,则说明两个链表相交,否则不相交。

    若两链表相交,我们可知pos2肯定是两个链表的一个相交点,将这个点看做两个链表的终止节点,使用我们上面提到的记录链表长度的解法,即可找到两个链表相交的第一个节点。

    并且需要提示一点的是,如果两个带有环的链表相交,则这两个链表的环肯定是同一个环。
    想不通的话可以在纸上画画,你会发现若相交,只会出现这一种情况。

    代码示例:

    // 判断链表是否存在环
    Link* hasCycle(Link* head)
    {
        Link *fast, *slow;
        slow = fast = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
                return slow;
        }
        return NULL;
    }
    
    Link* findFirstCross(Link* head1, Link* head2)
    {
        Link* pos1 = hasCycle(head1);  
        Link* pos2 = hasCycle(head2); 
    
        // 两个链表都有环
        if (pos1 && pos2)
        {
            // 判断这两个环是不是同一个环
            Link *tmp = pos1;
            do
            {
                if (pos1 == pos2 ||pos1->next == pos2)
                    break;
                pos1 = pos1->next->next;
                tmp = tmp->next;
            }while (pos1!=tmp);
            // 两个链表的环不是同一个环,所以没有交点
            if (pos1 != pos2 && pos1->next != pos2)
                return NULL;
            // 两个链表有共同的交点pos1,现在求第一个交点
            int len1, len2;
            len1 = len2 = 0;
            Link *nd1, *nd2;
            nd1 = head1;
            while (nd1 != pos1) {len1++;nd1=nd1->next;}
            nd2 = head2;
            while (nd2 != pos1) {len2++;nd2=nd2->next;}
            // 较长链表的链表的nd先走dif步
            int dif;
            nd1 = head1; nd2 = head2;
            if (len1 >= len2)
            {
                dif = len1 - len2;
                while (dif--) nd1 = nd1->next;
            }
            else
            {
                dif = len2 - len1;
                while (dif--) nd2 = nd2->next;
            }
            // 之后两个nd再一起走,直到nd相等(即为第一个交点)
            while (nd1!=pos1 && nd2!=pos1)
            {
                if (nd1 == nd2)
                    return nd1;
                nd1 = nd1->next;
                nd2 = nd2->next;
            }
            return pos1;
        }
    }
    展开全文
  • 判断两个可能有环的链表是否有交点两个单链表相交的一系列问题首先需要判断单链表是否有环hashSet(很简单,不多说,空间复杂度O(n))快慢指针接下来就需要解决有无交点的问题:两个无环链表是否有交点两个有环链...
  • 1、判断两个链表是否有环 case1:一个有环一个无环——-一定不相交 case2:两个都无环————–直接判断两个链表的最后一个结点是否相等 case3:两个都有环————–看其z点是否在另一个链表上
  • 链表的分类 链表主要分为三类: 单向链表只能从表头到表尾的顺序,每个节点中保存了指向下一...判断两个链表是否相交并找出交点 问题描述: 一个比较经典的问题,判断两个链表是否相交,如果相交找出他们的交点。 解...
  • 一个比较经典的问题,判断两个链表是否相交,如果相交找出他们的交点。 思路: 1、碰到这个问题,第一印象是采用hash来判断,将两个链表的节点进行hash,然后判断出节点,这种想法当然是可以的。 2、当然采用...
  • 问题描述:一个比较经典的问题,判断两个链表是否相交,如果相交找出他们的交点。思路:1、碰到这个问题,第一印象是采用hash来判断,将两个链表的节点进行hash,然后判断出节点,这种想法当然是可以的。2、当然采用...
  • 如果两个链表有交点那么代表这两个链表是一个Y型的链表 Y型的链表代表这两的链表的尾地址是相同的 如何能快速的的找到这个交点的位置呢? 首先我们可以确定的是两个普通单向链表的长度 当这两个普通单向链表...
  • 两个链表无非一长一短或者是两个一样长,单链表的长度对应着路程的一部分,所以无需再分辨两个链表的哪个长哪个短,确定的是这里要定义两个引用来遍历两个单链表。使用pA,pB分别代表两个链表的表头(无所谓长短)。...
  • 一、解决这个问题之前我们需要了解下如何判断个链表有环? 下面提供二种方法进行实现: 使用快慢指针,p1为快指针,p2为慢指针,让这两个指针指向链表的头部,让p1每次走一步,p2每次走两步,如果p1和p2相交,...
  • 判断两个链表是否相交:(假设两个链表都没有环) 1、判断第一个链表的每个节点是否在第二个链表中 2、把第二个链表连接到第一个后面,判断得到的链表是否有环,有环则相交 3、先遍历第一个链表,记住最后一个节点,...
  • 解题思路 情况1:两个链表均不含有环 ...可以对第一 个链表的节点地址进行hash排序,建立hash,然后针对第二个链表的每个节点的地址查询hash,如果它在hash中出现,则说明两个链表有共 同的结点。这个方法
  • 点击链接:判断两个链表是否相交并找出交点问题描述:一个比较经典的问题,判断两个链表是否相交,如果相交找出他们的交点。第一种情况:两个链表均不含有环 思路:1、直接法采用暴力的方法,遍历两个链表判断...
  • // 得到两个链表的差 diff = Math. abs (n1Num - n2Num); // 比较两段链表的长度,长的为n1 短的为n2 if (n1Num > n2Num) { n1 = node1; n2 = node2; } else { n1 = node2; n2 = node1; } /...
  • 链表是否相交分为以下三种情况: 1.两个单链表都不带环 2.只有一个单链表带环 3.两个单链表都带环 #pragma once #include #include struct ListNode{ int value; ListNode* ...
  • 如果两个链表均带环:(以下两种相交的情况) 如何判断链表是否带环,以及如何求环的入口点 判断两个带环单链表是否相交:   分别判断两个单链表p1,p2是否带环,返回快慢指针的交点(此交点必在环内)meet...
  • 判断两个单向链表是否有相交,并找出交点
  • 问题描述:一个比较经典的问题,判断两个链表是否相交,如果相交找出他们的交点。(注意两个单链表相交不会出现X型交叉——单链表,每个节点只有一个指针域)。第一种情况:两个链表均不含有环解题思路:1、直接法:...
  • 判断两个链表是否有交点 在1的基础上,求两个链表交点; 1. 判断两个链表是否有交点 总结了三种方法 利用hashset的方法 def has_insection_3(headA): """ 也可以使用hash_set, 如果 """ s = set() while...
  • 问题描述:判断两个链表是否相交,并求出交点。简单分析:考虑到链表是否带环的问题,可分为3种情况,1、两个链表都不带环2、其中一个链表带环(根本就不可能相交)3、两个链表带环下面具体情况具体分析 注:判断链表...
  • 判断两个链表是否相交:(假设两个链表都没有环) 1、判断第一个链表的每个节点是否在第二个链表中 2、把第二个链表连接到第一个后面,判断得到的链表是否有环,有环则相交 3、先遍历第一个链表,记住最后一个...
  • //判断两个链表有交点 typedef int DataType; struct ListNode{ DataType val; struct ListNode* next; }; typedef ListNode Node; //带环:两个链表都带环 //不带环:两个链表都不带环 //1.先判断两个链表...
  • 判断两个链表是否有环(两种方法,辅助hashset或用快慢指针),找到入环点 两个都无环,判断相交(两种方法,辅助hashse或计算链表长度差N然后长链先走N步,然后一起走,相遇即为交点) 两个都有环(一个有...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,934
精华内容 2,773
关键字:

如何判断两个链表是否有交点