[算法][C++]如何在不改变原有链表的情况下判断两个单项链表的相交点

喜欢ヅ旅行 2022-10-19 12:40 10阅读 0赞

原题目,在不改变两条单项链表的情况下,判断相交点.  
据说是字节跳动的面试Easy题.

class Node
    { 
    public:
        int data;
        Node* next;
        Node(int data, Node* nextP = nullptr) :data(data), next(nextP)
        { }
    };

先写一个节点类

Node* sameAddress{  new Node{ 666,new Node{ 4,new Node{ 5}}} };
        Node No_1{  1,new Node{ 2,new Node{ 3,new Node{ 555,sameAddress}}} };
        Node No_2{  11,new Node{ 22,new Node{ 33,new Node{ 489,new Node{ 449,new Node{ 1556,sameAddress}}}}} };

接着手搓一两条相交的链表

可以通过快慢指针的差速来解决.

下面附解题源码.  
tmp1和tmp2各自对应两条链表的头节点

while(p1->next!=p2)
        { 
            if (p1->next)
                p1 = p1->next;
            else
                p1 = tmp1;
            if (p2->next->next)
                p2 = p2->next->next;
            else
                p2 = tmp2;
        }

可读性高的版本

while (p1->next != p2)
    	{ 
    		p1->next ? p1 = p1->next : p1 = tmp1;
        	p2->next->next ? p2 = p2->next->next : tmp2;
        }

使用三目运算符简洁版本

while (p1->next != p2)
            (p2->next->next ? p2 = p2->next->next : tmp2) && (p1->next ? p1 = p1->next : p1 = tmp1) ;

使用三目运算符加逻辑运算的超简洁版本

发表评论取消回复

表情：

评论列表（有 0 条评论，10人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java 判断两个链表是否相交

文章目录问题描述方法一方法描述动画演示代码如下时间复杂

忘是亡心i/ 2023年10月09日 13:45/ 0 赞/ 84 阅读

相关判断两个链表是否相交

JAVA堆和栈比较两个链表，判断是否相交，找出相交的第一个点？首先应该清楚两个单链表相交要么都是无环链表，要么都是有环链表，不存在一个有环链表和一个无环链表相交

朴灿烈づ我的快乐病毒、/ 2023年06月18日 02:58/ 0 赞/ 46 阅读

相关每日一题--判断两个链表相交

今天这道是面试中的高频题，有关链表和树的操作一直都是面试官比较喜欢考的，因为链表和树的操作涉及到指针的使用，面试官可以通过算法题的形式短时间内考察一个人对指针的熟练程度。话不多

悠悠/ 2023年02月26日 13:27/ 0 赞/ 102 阅读

相关 [算法][C++]如何在不改变原有链表的情况下判断两个单项链表的相交点

原题目,在不改变两条单项链表的情况下,判断相交点. 据说是字节跳动的面试Easy题. class Node { public:

喜欢ヅ旅行/ 2022年10月19日 12:40/ 0 赞/ 11 阅读

相关判断两个链表是否相交以及如何找到它们相交的第一个结点

//判断两个链表是否相交 public static boolean isIntersect(Node node1,Node node2){

向右看齐/ 2022年10月01日 12:48/ 0 赞/ 171 阅读

相关编程之美-判断两个链表是否相交

第三章　3.6 编程判断两个链表是否相交问题详细描述: 给出两个单向链表的头指针（如图3-8所示），比如h1、h2，判断这两个链表是否相交。这里为了简化问题，我们

偏执的太偏执、/ 2022年08月04日 12:49/ 0 赞/ 226 阅读

相关有环单链表相交判断、单链表相交判断

有环单链表相交判断单链表相交判断 -------------------- 有环单链表相交判断如何判断两个有环单链表是否相

柔光的暖阳◎/ 2022年06月09日 04:59/ 0 赞/ 264 阅读

相关判断两个单链表是否相交及找到第一个交点

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

我不是女神ヾ/ 2022年06月03日 08:56/ 0 赞/ 188 阅读

相关 10.两个单链表相交，计算相交点

思路在8中有介绍分别计算两链表的长度，为M，N。让指向长链表的指针先走，让两链表等长，再两指针一起走，第一次相遇点即为相交点。如果把相交链表变成一个环，则环的第一个

╰半橙微兮°/ 2022年05月26日 10:15/ 0 赞/ 210 阅读

相关 9.判断两个单链表是否相交

只介绍O（n）算法思路1：将链表1中各结点地址存入HashTable中，再遍历链表2，如果有结点已经在HashTable中，则两链表相交。思路2：

不念不忘少年蓝@/ 2022年05月26日 10:12/ 0 赞/ 251 阅读