当前位置：
  1. 首页
  2. 剑指offer刷题第三期
  3. 问题详情

【链表专题】剑指 Offer 52. 两个链表的第一个公共节点

本问题对应课程链接：剑指offer刷题第三期

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi
369 88

共以下 88 个回答

  • 招舟子 普通 2023年8月24日 下午5:52

    /**
    * Definition for singly-linked list.
    * public class ListNode {
    * int val;
    * ListNode next;
    * ListNode(int x) {
    * val = x;
    * next = null;
    * }
    * }
    */
    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode a = headA,b= headB;
    while(a!=b){
    if(a!=null){
    a = a.next;
    }else{
    a = headB;
    }
    if(b!=null){
    b = b.next;
    }else{
    b = headA;
    }
    }
    return a;
    }
    }加油

    0 赞同 0 条回复
  • mpweixin用户 普通 2023年7月17日 下午10:11

    时间: O(n+m)
    空间: O(1)
    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if(headA null || headB null){
    return null;
    }
    ListNode A = headA;
    ListNode B = headB;
    while(A != B){
    A = A null ? headB : A.next;
    B = B     null ? headA : B.next;
    }
    return A;
    }
    }

    0 赞同 0 条回复
  • 橙子陈 普通 2023年7月15日 下午5:36 
    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (null == headA || null == headB) return null;
        ListNode A = headA;
        ListNode B = headB;
        while (A!=B){
            A = (null == A) ? headB : A.next;
            B = (null == B) ? headA : B.next;
        }
        return A;
    }
}

    时间复杂度O(n+m)
    空间复杂度O(1)

    0 赞同 0 条回复
  • ZJS 永久会员 2023年7月9日 下午5:09

    思路：将两个链表拼在一起，将公共部分对其，然后遍历
    时间复杂度：O(n + m)
    空间复杂度：O(1)

    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null)
            return null;

        ListNode p1 = headA, p2 = headB;

        while(p1 != p2){
            // 这里需要注意，判读是否为空应该是p1 == null,而不是p1.next == null
            // 这样才能做到如果没有公共节点时退出循环
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA : p2.next;
        }

        return p1;
    }
}
    0 赞同 0 条回复
  • 一琬人间烟火 普通 2023年7月7日 下午9:49

    先对齐，然后找共同点：
    c++

    class Solution {
    public:
    ListNode getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode     curA=headA;
    ListNode* curB=headB; //必须定义，后面要用到原始的数据
    int l1=0,l2=0;
    while(curA!=NULL){
    l1++;
    curA=curA->next;
    }
    while(curB!=NULL){
    l2++;
    curB=curB->next;
    }

        curA=headA;
    curB=headB;
    if(l2>l1){
        swap(l2,l1);
        swap(curA,curB);
    } 
    int gap=l1-l2;
    while(gap--){
        curA=curA->next;
    }
    while(curA!=NULL){
        if(curA==curB){
            return curB;
        }
        curB=curB->next;
        curA=curA->next;
    }
    return NULL;
}

    };

    0 赞同 0 条回复
  • cute. 普通 2023年7月5日 上午9:26

    思路：双指针同时前进，找相同点

    var getIntersectionNode = function(headA, headB) {
    let a = headA;
    let b = headB;
    while (a != b) {
        a = a !== null ? a.next : headB;
        b = b !== null ? b.next : headA;
    }
    return a;
};
    0 赞同 0 条回复
  • 与你同行 普通 2023年7月3日 上午11:23

    时间复杂度：O(n)
    空间复杂度：O(1)

    /**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    var lenA int
    var lenB int
    n1 := headA
    n2 := headB

    for n1 != nil {
        n1 = n1.Next
        lenA++
    }
    for n2 != nil {
        n2 = n2.Next
        lenB++
    }

    //两者进行对齐
    n1 = headA
    n2 = headB
    if lenA > lenB {
        for i:=0; i< lenA - lenB; i++ {
            n1 = n1.Next
        }
    }else{
        for i:=0; i< lenB - lenA; i++ {
            n2 = n2.Next
        }
    }

    //开始对比两个节点是否相同
    for n1 != nil && n2 != nil && n1 != n2 {
        n1 = n1.Next
        n2 = n2.Next
    }

    if n1 == nil || n2 == nil{
        return nil
    }else{
        return n1
    }
}
    0 赞同 0 条回复
  • mpweixin用户 永久会员 2023年7月1日 上午12:30

    代码

    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null)return null;
        ListNode tempA=headA;
        ListNode tempB=headB;

        while(tempA!=tempB){
            tempA=tempA==null?headB:tempA.next;
            tempB=tempB==null?headA:tempB.next;
        }
        return tempA;
    }
}
    0 赞同 0 条回复
  • dys 普通 2023年6月28日 下午10:50

    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA null || headB null){
    return null;
    }
    ListNode new1 = headA;
    ListNode new2 = headB;
    ListNode new3 = headA;
    ListNode new4 = headB;
    int i = 0;
    while (new1 != null){
    new1 = new1.next;
    i++;
    }
    int j = 0;
    while (new2 != null){
    new2 = new2.next;
    j++;
    }
    if (i > j){
    for(int a = 0; a < i – j; a++){
    new3 = new3.next;
    }
    }else if(i < j){
    for(int a = 0; a < j – i; a++){
    new4 = new4.next;
    }
    }
    return abc(new3,new4);
    }

    public ListNode abc(ListNode new3,ListNode new4){
    while (new3 != null){
        if (new3 != new4){
            new3 = new3.next;
            new4 = new4.next;
        }else{
            return new3;
        }
    }
    return null;
}

    }

    时间复杂度：O(a+b+c+d)四个链表的遍历总次数 空间复杂度：O(1)

    0 赞同 0 条回复
  • 淡色 花樱 普通 2023年6月28日 下午6:51

    ““java
    class Solution{
    ListNode getIntersectionNode(ListNode headA,ListNode headB){
    if(headAnull||headB null) return null;
    ListNode A = headA;
    ListNode B = headB;
    while(A!=B){
    A=A null?headB:A.next;
    B=B    null?headA:B.next;
    }
    return A;
    }
    }
    如果到达最后一个节点，则重新遍历另外一个链表，直到相交

    0 赞同 0 条回复
  • 昂立的狼 普通 2023年6月28日 下午4:22

    时间复杂度O（n）
    空间复杂度O(1)
    结果链表，用双指针表示，一个头指针，一个更新指针，
    循环比较两个链表，把两个链表中小的值，逐个更新进结果链表，直到其中一个链表为空，则把另外一个链表直接放结果链表后面

            class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        res = ListNode(0)
        res2 = res
        while l1 and l2:
            if l1.val > l2.val:
                res2.next = l2
                l2 = l2.next
            else:
                res2.next = l1
                l1 = l1.next
            res2 = res2.next

        if l1:
            res2.next = l1
        else:
            res2.next = l2

        return res.next
    0 赞同 0 条回复
  • 浅伤 永久会员 2023年6月28日 下午4:12

    时间复杂度O(n)
    空间复杂度O(1)
    b设置双指针遍历两条链表得到长度
    相减，长的链表先走
    然后两个指针再同时走
    相同是相遇，返回结果

    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a=headA, b=headB;

        int la=0, lb=0;
        while(a!=null && la++ >= 0) a = a.next;
        while(b!=null && lb++ >= 0) b = b.next;

        int d = la - lb;
        if(d>0){
            while(d-- > 0){
                headA = headA.next;
            }
        }
        else if(d<0){
            d = -d;
            while(d-- > 0){
                headB = headB.next;
            }
        }

        while(headA!=headB){
            headA = headA.next;
            headB = headB.next;
        }

        return headA;
        }               
}
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月28日 下午1:06 
    java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) {
            return null;
        }
        //A走完后转到B，B走完后转到A，如果有共同节点这时候就会相遇
        ListNode A = headA, B = headB;
        while(A != B) {
            A = (A == null) ? headB : A.next;
            B = (B == null) ? headA : B.next;
        }
        return A;
    }
}

    时间复杂度O(A+B), 空间复杂度O(1)

    0 赞同 0 条回复
  • 大大 普通 2023年6月28日 上午9:24 
    class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* headA1=headA;
        ListNode* headB1=headB;

        while(headA!=headB){  
           headA= headA!=NULL?headA->next:headB1;
           headB= headB!=NULL?headB->next:headA1;            
        }
       return headA;
    }
};
    0 赞同 0 条回复
  • Jerry 普通 2023年6月27日 下午11:26 
    //双指针
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) { //直到二者相遇
            A = A != null ? A.next : headB; // A链表遍历完，就接去 B链表的头节点
            B = B != null ? B.next : headA; // B链表遍历完，就接去 A链表的头节点
        }
        return A;
    }
}

    时间复杂度：O(m+n)
    空间复杂度：O(1)

    0 赞同 0 条回复
  • Lucky 普通 2023年6月27日 下午4:31

    python3实现
    class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
    node1, node2 = headA, headB

        while node1 != node2:
        node1 = node1.next if node1 else headB
        node2 = node2.next if node2 else headA

    return node1
    0 赞同 0 条回复
  • 泡芙 永久会员 2023年6月26日 下午5:26

    用 p1 遍历 head A， p2 遍历 headB， 如果 p1等于null ，就去走 p2 走过的路（遍历 head B），如果 p2等于null ，就去走 p1 走过的路（遍历 head A）, 此时 p1 和 p2 走了同样的路。如果这两条路上有相交的节点，即 p1等于p2，返回其中任意一个节点，没有则返回 null
    Time：O(M+N)
    Space：O(1)

    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode p1 = headA;
        ListNode p2 = headB;

        while (p1 != p2) {
            if (p1 != null) {
                p1 = p1.next;
            } else {
                p1 = headB;
            }

            if (p2 != null) {
                p2 = p2.next;
            } else {
                p2 = headA;
            }
        }
        return p1;
    }
}
    0 赞同 0 条回复
  • Gracelyne 普通 2023年6月25日 下午3:51

    time O(n)
    memory O(1)

    class Solution {
public:
    int getLength(ListNode *node){
        int count = 0;
        while(node){
            count++;
            node = node->next;
        }
        return count;
    }
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //1. 得到长度
        int lenA = getLength(headA);
        int lenB = getLength(headB);
        int k = (lenA >= lenB) ? lenA-lenB : lenB-lenA;
        //2. 较长的link缩短k
        ListNode *lA = headA;
        ListNode *lB = headB;
        while(k > 0 && lenA >= lenB){
            k--;
            lA = lA->next;
        }
        while(k > 0 && lenA < lenB){
            k--;
            lB = lB->next;
        }
        //3. 确认是否为相交链表
        while(lA && lB){
            if(lA == lB) return lA;
            lA = lA->next;
            lB = lB->next;
        }
        return NULL;
    }
};
    0 赞同 0 条回复
  • Yangon 普通 2023年6月25日 上午11:06

    公共节点

    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;
        while(a != b){
            a = a != null ? a.next : headB;
            b = b != null ? b.next : headA;
        }

        return a;

    }
}
    0 赞同 0 条回复
  • 往远处看 普通 2023年6月24日 下午10:19

    解题思路

    首先将两个链表的头节点定义指针，指向头节点，两个指针分别往后移动，当他们指向的值是相同的时候停止。

    代码

    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == nullptr ||headB == nullptr) return nullptr;
        ListNode *A = headA;
        ListNode *B = headB;
        while(A != B)
        {
            A = A ==nullptr ?headB:A->next;
            B = B ==nullptr ?headA:B->next;
        }
        return A;

    }
};
    0 赞同 0 条回复
  • baoyou 普通 2023年6月24日 下午7:46 
    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode A = headA;
        ListNode B = headB;
        while (A != B) {
            A = A == null ? headB : A.next;
            B = B == null ? headA : B.next;
        }
        return A;
    }
}

    双指针

    0 赞同 0 条回复
  • HU 普通 2023年6月24日 下午7:36 
    /**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    // 如果两个链表有一个链表为空，则返回空
    if(headA === null || headB === null) return null;
    let A = headA;
    let B = headB;

    // 终止条件A == B
    // 第一种为A == B == null，这种情况下返回A为返回null。
    // 第二种为A == B == 1stCommonNode。
    while(A != B) {
        A = A == null? headB : A.next;
        B = B == null? headA : B.next;
    }

    return A;
};

    时间复杂度：O(A + B)。
    空间复杂度：O(1)。

    0 赞同 0 条回复
  • 已断网的Blue 普通 2023年6月24日 上午10:14

    两个链表走到底后，交换 走的路程是一样的。

    class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p = headA, *q = headB;
        while(p != q){
            if(p) p = p->next;
            else p = headB;


<pre><code>        if(q) q = q->next;
        else q = headA;
    }

    return p;

}
</code></pre>

};
    0 赞同 0 条回复
  • 未来已来~ 普通 2023年6月23日 下午11:08 
    /** Java 代码
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 1.空链表情况处理
        if (headA == null || headB == null) {
            return null;
        }
        // 2. 循环遍历俩链表,直到第一次相遇
        ListNode A = headA;
        ListNode B = headB;

        while ( A != B) {
            A = A == null ? headB : A.next; // 当 A 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点,否则继续遍历,以下同
            B = B == null ? headA : B.next;
        }
        // 3. 当它们相遇时，所指向的结点就是第一个公共结点,返回
        return A; // return B
    }
}

    复杂度分析:
    时间复杂度: O(A+B)
    空间复杂度: O(1)

    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月23日 下午9:31

    双指针均走两条链表

    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null) {
            return null;
        }
        if (headB == null) {
            return null;
        }

        ListNode nodeA = headA;
        ListNode nodeB = headB;

        while(nodeA != nodeB) {
                if (nodeA == null) {
                    nodeA = headB;
                } else if (nodeB == null) {
                    nodeB = headA;
                }else {
                    nodeA = nodeA.next;
                    nodeB = nodeB.next;
                }

        }
       return nodeA;
    }
}
    0 赞同 0 条回复
  • TT 永久会员 2023年6月22日 下午9:56

    双指针

    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null)
            return null;
        ListNode A = headA, B = headB;
        while(A != B) {
            A = A == null ? headB : A.next;
            B = B == null ? headA : B.next;
        }
        return A;
    }
}

    时间复杂度O(m+n)
    空间复杂度O(1)

    0 赞同 0 条回复
  • Yodl. 普通 2023年6月22日 下午9:06 
    //解一
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p,*q;
        p=headA;
        q=headB;
        int num_A=0,num_B=0,k;
        while(p!=NULL)
        {
            num_A++;
            p=p->next;
        }
        while(q!=NULL)
        {
            num_B++;
            q=q->next;
        }
        p=headA;
        q=headB;
        if(num_A>num_B)
        {
            k=num_A-num_B;
            while(k!=0)
            {
                p=p->next;
                k--;
            }
        }
        if(num_Anext;
                k--;
            }
        }
        while(p!=NULL)
        {
            if(p==q)
            {
                return p;
            }
            p=p->next;
            q=q->next;
        }
        return NULL;

    }
};

//解二
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* p1 = headA;
        ListNode* p2 = headB;
        bool count = 0;
        while(p1 != p2 && p1 != nullptr && p2 != nullptr){
            p1 = p1->next;
            p2 = p2->next;
            if(p1 == nullptr && count == 0){
                count = 1;
                p1 = headB;
            }
            if(p2 == nullptr){
                p2 = headA;
            }
        }
        if(p1 == p2) return p1;
        else return nullptr;
    }
};

    时间复杂度O(m+n)
    空间复杂度O（1）

    0 赞同 0 条回复
  • WhyBeBubble 普通 2023年6月22日 下午4:52

    “`C++实现
    /**
    * Definition for singly-linked list.
    * struct ListNode {
    * int val;
    * ListNode *next;
    * ListNode(int x) : val(x), next(NULL) {}
    * };
    */
    class Solution {
    public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode* ha = headA;
    ListNode* hb = headB;
    while (ha != hb) {
    ha = ha ? ha->next : headB;
    hb = hb ? hb->next : headA;
    }
    return ha;
    }
    };
    “`

    0 赞同 0 条回复
  • &Camille 普通 2023年6月22日 下午3:03

    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if (headA == null || headB == null) {
        return null;
    }
    ListNode tempA = headA;
    ListNode tempB = headB;

    //循环遍历两个链表，
    while(tempA!=tempB){
        tempA = tempA == null?headB:tempA.next;
        tempB = tempB == null?headA:tempB.next;
    }
    return tempA;
}

    }

    0 赞同 0 条回复
  • 等待 普通 2023年6月22日 下午2:28

    Java
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //非空判断
    if (headA null || headB null) {
    return null;
    }
    ListNode a = headA;
    ListNode b = headB;
    while (a != b) {
    if (a null) {
    a = headB;
    } else {
    a = a.next;
    }
    if (b     null) {
    b = headA;
    } else {
    b = b.next;
    }
    }
    return a;
    }
    时间复杂度O(m+n)
    空间复杂度O（1）

    0 赞同 0 条回复
  • 地平线真勇敢 普通 2023年6月22日 上午10:30 
    Java
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = length(headA);
        int lenB = length(headB);
        while(lenA != lenB){    //让长度较长的链表走多出的步数
            if(lenA > lenB){
                headA = headA.next;
                lenA--;
            }else{
                headB = headB.next;
                lenB--;
            }
        }
        while(headA!=headB){    //  同时走，如果有交点有返回值，没有交点返回null
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }

    private int length(ListNode node){ //求链表长度，链表遍历得到长度
        int length = 0;
        while(node != null){
            node = node.next;
            length++;
        }
        return length;
    }
时间复杂度o(n)
空间复杂度o(1)
    0 赞同 0 条回复
  • 短某人。 永久会员 2023年6月22日 上午1:07

    打卡

    class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        node1,node2 = headA,headB
        if not node1 and node2:
            return node1
        while node1 != node2:
            if node1:
                node1 = node1.next
            else:
                node1 = headB
            if node2:
                node2 = node2.next
            else:
                node2 = headA
        return node1
    0 赞同 0 条回复
  • CV大神 普通 2023年6月22日 上午12:29 
     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode currentA = headA;
        ListNode currentB = headB;
        //无论是否有重合的，他们走的长度是一致的，要么在重合点相遇，要么是两个指针都分别把两个链表遍历了
        while (currentA != currentB){
            currentA = currentA != null? currentA.next:headB;
            currentB = currentB != null? currentB.next:headA;
        }
        return currentA;
    }

    时间复杂度O(m+n)，空间复杂度O(1)

    0 赞同 0 条回复
  • GGBond 普通 2023年6月21日 下午10:02 
    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //方法一双指针：使链表尾部对齐，从对齐头处开始移动
        int a_len = getLength(headA);
        int b_len = getLength(headB);
        //保持A更长
        if(a_len < b_len){
            ListNode temp = headA;
            headA = headB;
            headB = temp;
        }
        for(int i = 0;i < Math.abs(a_len - b_len);i++){
            headA = headA.next;
        }
        while(headA != null && headB != null){
            if(headA == headB){
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }

    public int getLength(ListNode node){
        int count = 0;
        while(node != null){
            node = node.next;
            count++;
        }
        return count;
    }
}
//方法二：哈希表
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //使用哈希表，查找相同结点
        HashSet<ListNode> hash = new HashSet<>();
        while(headA != null){
            hash.add(headA);
            headA = headA.next;
        }
        while(headB != null){
            if(hash.contains(headB)){
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
    1 赞同 0 条回复
  • mpweixin用户 永久会员 2023年6月21日 下午7:55

    打卡

    var getIntersectionNode = function(headA, headB) {
    if(headA == null || headB == null) {
        return null;
    }

    let a = headA;
    let b = headB;
    while(a != b){
        if(a == null){
            a = headB;
        }else{
            a = a.next;
        }
        if(b == null){
            b = headA;
        }else{
            b = b.next;
        }
    }

    return a;
};
    0 赞同 0 条回复
  • 3_🔥 永久会员 2023年6月21日 下午4:44 
    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int a = 0,b = 0;
        ListNode aa = headA,bb = headB;
        while(aa!=null){
            a++;
            aa = aa.next;
        }
        while(bb!=null){
            b++;
            bb = bb.next;
        }
        int d = a - b;
        if(d>0){
            while(d-->0) headA = headA.next;
        }else if(d<0){
            d = -d;
            while(d-->0) headB = headB.next;
        }  
        while(headA!=headB){
            headA =headA.next;headB = headB.next;
        }
        return headA;
    }
}
//把多的先走了
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月21日 下午3:53

    双指针

    # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        l1 = headA
        l2 = headB
        while l1 != l2:
            l1 = l1.next if l1 else headB
            l2 = l2.next if l2 else headA
        return l1
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月21日 上午9:58 
    struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA==NULL||headB==NULL)
    {
      return NULL;
    }
    struct ListNode*a=headA,*b=headB;
    while(a!=b)
    {
        a = a == NULL ? headB : a->next;
        b = b == NULL ? headA : b->next;
    }

  return a;
}

    时间复杂度是O(m+n)
    空间复杂度为 O(1)

    0 赞同 0 条回复
  • 哈哈哈哈开开心心 普通 2023年6月21日 上午7:07 
    # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:

        if not headA or not headB:
            return None

        n1, n2 = headA, headB
        while n1 or n2:
            if n1 == n2:
                return n1
            elif not n1:
                n1 = headB
            elif not n2:
                n2 = headA
            else:
                # 用else再次检查表头为交点的情况
                n1 = n1.next
                n2 = n2.next

        return None
    0 赞同 0 条回复
  • zll 普通 2023年6月20日 下午10:43

    太妙了
    时间复杂度O（m+n）；
    空间复杂度O（1）；

    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(!headA||!headB)
        return NULL;
    struct ListNode *p,*q;
    p=headA;
    q=headB;
    while(p!=q){
        p=p==NULL? headB:p->next;
        q=q==NULL? headA:q->next;
    }

    return p;
}
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月20日 下午9:21 
    双指针
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        p = headA
        q = headB
        while p != q:
            p = headB if not p else p.next
            q = headA if not q else q.next
        return p
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月20日 下午7:56

    C++实现 节点数量之差实现 O(n) O(1)

    class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *a = headA;
        ListNode *b = headB;
        int numberA = 0;
        int numberB = 0;

        while(a != NULL){
            numberA++;
            a = a -> next;
        }
        while(b != NULL){
            numberB++;
            b = b -> next;
        }

        ListNode *l = headA;
        ListNode *s = headB;
        int k = abs(numberA - numberB);

        if(numberA < numberB){
            l = headB;
            s = headA;
        }

        for(int i = 0; i < k; i++){
            l = l -> next;
        }
        while(l != s){
            if(l == NULL || s == NULL) return NULL;
            l = l -> next;
            s = s -> next;
        }
        return s;        
    }
};
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月20日 下午7:49 
    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int len1=0,len2 = 0;
        ListNode temp1 = headA;
        ListNode temp2 = headB;
        while(temp1!=null){
            temp1 = temp1.next;
            len1++;
        }
        while(temp2!=null){
            temp2 = temp2.next;
            len2++;
        }
        int n = len1>len2?len1-len2:len2-len1;
        if(len1>=len2){
            for(int i =0;i<n;i++){
                headA = headA.next;
            }
            while(headA!=null){
            if(headA==headB){
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
            }
        }else{
            for(int i =0;i<n;i++){
                headB = headB.next;
            }
            while(headB!=null){
            if(headA==headB){
                return headB;
            }
            headA = headA.next;
            headB = headB.next;
            }
        }
        return null;
    }
}

    计算插值，直接遍历 O(n) O(1)

    0 赞同 0 条回复
  • 别恰冰水🧊 永久会员 2023年6月20日 下午7:05

    时间复杂度O（m+n）
    空间复杂度O（1）

    struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (headA NULL || headB NULL) {
    return NULL;
    }
    struct ListNode *l1 = headA;
    struct ListNode *l2 = headB;
    while (l1 != l2) {
    l1 = l1 NULL ? headB : l1->next;
    l2 = l2     NULL ? headA : l2->next;
    }
    return l1;
    }

    0 赞同 0 条回复
  •  普通 2023年6月20日 下午6:38 
    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode indeA = headA;
        ListNode indeB = headB;
        int indeALength = 0;
        int indeBLength = 0;
        while(indeA != null){
            indeALength++;
            indeA = indeA.next;
        }
        while(indeB != null){
            indeBLength++;
            indeB = indeB.next;
        }
        int deleteLength = indeALength - indeBLength;
        if(deleteLength > 0){
            for(int i =0;i<deleteLength;i++){
                headA = headA.next;
            }
        }
        if(deleteLength < 0){
            for(int i =0;i<(deleteLength*-1);i++){
                headB = headB.next;
            }
        }
        while(headA != null && headA != headB){
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }
}

    找公共节点，说明两个链表公共节点一样长，先将两个链表弄成一样的长度，然后进行比对

    0 赞同 0 条回复
  • 断舍离 永久会员 2023年6月20日 下午4:01 
    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //用于比较的临时节点
        ListNode A = headA;
        ListNode B = headB;

        //最终当A与B相等时，要么为null，即没有公共节点，要么为公共节点
        while(A != B){
            if(A == null){
                A = headB;
            }else {
                A = A.next;
            }
            if(B == null){
                B = headA;
            }else {
                B = B.next;
            }
        }
        return A;
    }
}
    0 赞同 0 条回复
  • BOZ 普通 2023年6月20日 下午3:17

    【思路】双指针，两个指针交叉遍历两个链表，两指针重合时即为答案
    【复杂度】时间O(m+n)，空间O(1)

    class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *tmpA = headA, *tmpB = headB;
        while (tmpA != tmpB) {
            tmpA = tmpA == NULL? headB: tmpA->next;
            tmpB = tmpB == NULL? headA: tmpB->next;
        }
        return tmpA;
    }
};
    0 赞同 0 条回复
  • Bello~ 普通 2023年6月20日 下午1:27

    时间复杂度O（m+n）
    空间复杂度O（1）

    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        while (cur1 ! cur2 ) {
            cur1 = cur1 != null ? cur1.next : headB;
            cur2 = cur2 != null ? cur2.next : headA;

        }
        return cur1;
    }
}
    0 赞同 0 条回复
  • 名字什么的好麻烦 普通 2023年6月20日 下午12:56

    时间复杂度：O(a+b)
    空间复杂度：O(1)

    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null)
            return null;
        ListNode a=headA,b=headB;
        while(a!=b){
            a= a==null ? headB:a.next;
            b= b==null ? headA:b.next;
        }
        return a;
    }
}
    0 赞同 0 条回复
  • 张开怀 普通 2023年6月20日 上午11:13 
    class Solution{
public:
     ListNode* getIntersectionNode(ListNode* headA, ListNode* headB){
           % 判断特殊情况，是否为空
           if(!headA || !headB)
              return nullptr;
           ListNode* A = headA;
           ListNode* B = headB;
           % 循环条件，两值是否相等
           while(A != B){
                % 为空，指向另一个链表的头结点
                % 不为空，则指向其下一个结点
                A = A ? A->next : headB;
                B = B ? B->next : headA;
           }
           return A;
     }
}

    时间复杂度：O(a+b)，a、b分别为两链表各自长度
    空间复杂度：O(1)

    0 赞同 0 条回复
  • 跋扈疙瘩汤 普通 2023年6月20日 上午10:21 
    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 要考虑头节点
        ListNode* cur1 = headA;
        ListNode* cur2 = headB;
        while(cur1 != cur2) {
            cur1 = (cur1) ? cur1->next : headB;
            cur2 = (cur2) ? cur2->next : headA;
        }
        return cur1;
    }
};
    0 赞同 0 条回复
  • 硬核洋葱 普通 2023年6月20日 上午9:53 
    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* pa = headA, *pb = headB;
        int numa = 0, numb = 0;
        while(pa){
            pa = pa->next;
            ++numa;
        }
        while(pb){
            pb = pb->next;
            ++numb;
        }

        if(numa < numb){
            pa = headB; pb = headA;
            swap(numa, numb);
        }
        else{
            pa = headA; pb = headB;
        }

        while(numa > numb){
            --numa;
            pa = pa->next;
        }
        while(pa != pb){
            pa = pa->next;
            pb = pb->next;
        }
        return pa;
    }
};

    时间复杂度O(m+n)，空间复杂度O(1)
    先求出链表长度的差值。令长度较长的那个链表先走过这段距离，对齐两个链表之后，同时遍历，就能找到公共节点了

    0 赞同 0 条回复
  • 花老爷 普通 2023年6月20日 上午9:46

    只要走过两个链表长度的差值之后，如果有公共节点同步走一定会相遇
    时间：O(m+n)
    空间：O(1)

    public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA, curB = headB;
        int countA = 0, countB = 0;
        while (curA != null) {
            countA++;
            curA = curA.next;
        }
        while (curB != null) {
            countB++;
            curB = curB.next;
        }
        ListNode newA = headA, newB = headB;
        if (countA <= countB) {
            for (int i = 0; i < countB - countA; i++) {
                newB = newB.next;
            }
        } else {
            for (int i = 0; i < countA - countB; i++) {
                newA = newA.next;
            }
        }
        while (newA != null) {
            if (newA == newB) {
                return newA;
            }
            newA = newA.next;
            newB = newB.next;
        }
        return null;
    }
}
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月20日 上午4:09

    c++
    双指针，每个指针指向一个链表的头节点，一个链表遍历完了，指向另一个指针的头节点。如果有公共节点，必然会相遇，否则两个最终都会指向NULL，返回NULL
    TC: O(n)
    SC: O(1)

    class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *currA = headA;
        ListNode *currB = headB;
        while (currA != currB) {
            currA = currA ? currA->next : headB;
            currB = currB ? currB->next : headA;
        }
        return currA;
    }
};
    0 赞同 0 条回复
  • 彦，，# 普通 2023年6月20日 上午12:33

    唉 不够浪漫

    class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(NULL == headA || NULL == headB) return  NULL;
        ListNode *A = headA, *B = headB;
        while(A)
        {
            while(B)
            {
                if( A == B) return  A; 
                B =B->next;
            }
            B = headB;
            A =A->next;
        }
        return NULL;
    }
};
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月20日 上午12:11

    第二圈交换起跑线

    “`c#
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
    if(headA == null || headB == null){
    return null;
    }

        ListNode A = headA;
    ListNode B = headB;

    while(A != B){
        A = A == null ? headB : A.next;
        B = B == null ? headA : B.next;
    }


    return A;
}

    “`

    0 赞同 0 条回复
  • 　　　　　　　　 普通 2023年6月20日 上午12:02 
    class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* p=headA,*q=headB;
        while(p!=q){
            if(!p)p=headB;
            else p=p->next;
            if(!q)q=headA;
            else q=q->next;
        }
        return p;
    }
};

    【时间O(m+n),空间O(1)】
    第一条视为a+c段，第二条视为b+c段
    a+c+b+c=b+c+a+c
    相遇在最后一个c段的起点
    不相遇则c段起点为空指针

    0 赞同 0 条回复
  • 大鑫啊 普通 2023年6月19日 下午11:59

    时间复杂度：O(n+m)
    空间复杂度：O(1)
    1、先判断两个链表是否为空
    2、创建两个虚拟节点A、B，指向两个链表头结点
    3、在A B不相等的条件下循环（某一个虚拟结点为空则该结点指向另一个链表头结点继续循环，否则指向自己的next结点）
    4、（如果有共同结点则返回A或者B即可，没有共同结点会返回空）

    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode A = headA;
        ListNode B = headB;
        while(A != B){
            A = A == null ? headB : A.next;
            B = B == null ? headA : B.next;
        }
        return A;
    }
}
    0 赞同 0 条回复
  • 残月冷骄阳 普通 2023年6月19日 下午11:59 
    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {

<pre><code>    ListNode A = headA, B = headB;
</code></pre>

if(headA<span class="text-highlighted-inline" style="background-color: #fffd38;">null || headB </span>null){
    return null;
}

//两个链表如果没有相交的时候，两个node遍历完两个链表后，就会同时为null，此时A<span class="text-highlighted-inline" style="background-color: #fffd38;">B；
//如果相交，走相同的步数后，A</span>B的时候，就是第一次相交点
    while(A!=B){
    A = A !=null ? A.next:headB;
    B = B !=null ? B.next:headA  ;<br />
    }
    return A;
    }
}
    0 赞同 0 条回复
  • Tral-JQ 普通 2023年6月19日 下午11:57

    时间复杂度：O(m+n)
    空间复杂度：O（1）

    class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *node1 = headA;
        ListNode *node2 = headB;

        while (node1 != node2) {
            node1 = node1 != NULL ? node1->next : headB;
            node2 = node2 != NULL ? node2->next : headA;
        }
        return node1;

    }
};
    0 赞同 0 条回复
  • 张君雅小妹妹 普通 2023年6月19日 下午11:47

    时间复杂度：O(m + n)
    空间复杂度：O(1)

    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode tmpA = headA;
        ListNode tmpB = headB;
        while(tmpA.next != null && tmpB.next != null){
            tmpA = tmpA.next;
            tmpB = tmpB.next;
        } 
        // 计算相差的步数
        int step = 0;
        if(tmpA.next != null){
            while(tmpA.next != null){
                tmpA = tmpA.next;
                step++;
            }
             // 交换，让headB成为更长的那个
            ListNode tmp = headA;
            headA = headB;
            headB = tmp;
        } else{
            while(tmpB.next != null){
                tmpB = tmpB.next;
                step++;
            }
        }
        // 让长的链表先走step步
        while(step-- > 0){
            headB = headB.next;
        }

        while(headA != null && headB != null){
            if(headA == headB){
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}
    0 赞同 0 条回复
  • yxy 普通 2023年6月19日 下午11:45

    有难度

    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int count1=0, count2=0;
        ListNode *p1 = headA;
        ListNode *p2 = headB;
        while(p1)
        {
            count1++;
            p1=p1->next;
        }
        while(p2)
        {
            count2++;
            p2=p2->next;
        }
        if(count1>count2)
        {
            int diff = count1-count2;
            while(diff--)
                headA=headA->next;
        }
        else
        {
            int diff = count2-count1;
            while(diff--)
                headB=headB->next;
        }
        while(headA&&headB)
        {
            if(headB==headA)
                return headB;
            headA=headA->next;
            headB=headB->next;
        }
        return nullptr;
    }
};
    0 赞同 0 条回复
  • 怀瑾 永久会员 2023年6月19日 下午11:39

    C++
    执行用时： 40 ms
    内存消耗： 14.3 MB
    两个链表的第一个公共节点：
    所谓公共节点，就是地址相同的两个节点，因此需要使用判断，由于两个链表的长度不定，因此采用循环遍历的方式，创建两个辅助头节点，当链表A遍历完后会转向链表B的头节点，同时链表B遍历完后会转向链表A的头节点，循环一次后，两个辅助头节点必然相同，要么相遇，要么为NULL，返回即可。

    class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == NULL && headB == NULL) return NULL;
        ListNode *h1 = headA;
        ListNode *h2 = headB;
        while(h1!=h2){
            h1 = h1 == NULL ? headB : h1->next;
            h2 = h2 == NULL ? headA : h2->next;
        }
        return h1;
    }
};
    0 赞同 0 条回复
  • 哈哈哈 普通 2023年6月19日 下午11:35
    • 思路：坦然说，这道题其实我连题目都没get到，看了帅地的题目讲解才明白原来节点相同和值相同不是一回事（我是菜只因）。按照帅地其中一种思路的话，即在两个节点不相同时，然两个节点以1的步长走，直至null；当A为null时，赋值为headB;当B为null时，赋值为headA,继续走，两个节点总会有相交的时候，如果两个链表都走完还无法相等的话，证明二者不想交。
    • 时间复杂度为O（headA.length+headB.length）,空间复杂度为O（1）
    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      if(headA==null||headB==null)
      return null;
      ListNode A=headA;
      ListNode B=headB;
    //   while(A!=B){
    //       if(A==null){
    //           A=headB;
    //       }else{
    //           A=A.next;
    //       }
    //       if(B==null){
    //          B=headA;
    //       }else{
    //          B=B.next;
    //       }
    //   }
    while(A!=B){
        A = A == null ? headB : A.next;
        B = B == null ? headA : B.next;
    }
      return B;
    }
}
    0 赞同 0 条回复
  • 钱杰 普通 2023年6月19日 下午11:11

    class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
    if not headA or not headB:
    return None
    p1,p2=headA,headB
    while p1!=p2:
    if p1:
    p1=p1.next
    else:
    p1=headB
    if p2:
    p2=p2.next
    else:
    p2=headA
    return p1
    ”’
    1如果两个链表有一个为空，那就没有公共节点，直接返回None
    2设立两个指针p1,p2分别指向各自头结点
    3如果指向的两个节点不相等的时候，p1不为空，指向下一个，p1如果为空，居然是走p2指向的链表，p2同理
    4直到双方相等，也就是p1=p2,返回p1，此时也就是公共节点部分
    时间复杂度o(m+n),空间复杂度o(1)
    ”’

    0 赞同 0 条回复
  • Tang 普通 2023年6月19日 下午10:59 
    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 如果两个链表中有一个链表为null，那就不会有公共节点，返回null
        if (headA == null || headB == null) {
            return null;
        }
        /* 如果有公共节点
            headA的长度为m，headB的长度为n，公共节点的长度为c，headA的不公共节点长度为a，headB的不公共节点长度为b. 可会出现：a + c = m, b + c = n
            都从头节点开始遍历，A = headA, B = headB
            第一种可能：a = b，那必然会同时遍历到第一个公共节点。只要A==B，那就是遍历到了第一个公共节点
            第二中可能：a != b，因为长度不相等，会有一个链表先遍历到null,此时A=headB,或者B=headA.当A遍历过
            a + c + b + 1个节点（遍历过a+b+c次），也就是遍历到headB的第b+1个节点（也就是headB中第一个公共节点）时，B也遍历过 b + c + a + 1个节点（遍历过b+c+a次），也就是遍历到headB的第a+1个节点，此时A=B，遍历到第一个公共节点
        没有公共节点
            第一种情况：m = n，A和B同时到达链表的尾节点，最后A和B都为null
            第二种情况：m != n，A遍历过m + n次达到headB的尾节点null，B遍历过n + m次达到headA的尾节点null
        */
        ListNode A = headA, B = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next :headA;
        }
        return A;
    }
}

    时间复杂度：O(m+n) 空间复杂度：O(1)

    0 赞同 0 条回复
  • 阿白 普通 2023年6月19日 下午10:55

    思路：看了解析
    复杂度

    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode h1 = headA;
        ListNode h2 = headB;
        while(h1 != h2) {
            h1 = h1 == null ? headB : h1.next;
            h2 = h2 == null ? headA : h2.next;
        }
        return h1;


    }
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月19日 下午10:54

    1.创建两个指针A和B，分别指向输入链表headA和headB的头节点。
    2.使用while循环，只要A和B不相等（即还没有找到交点），就进行以下操作：
    （2.1）如果A不为空，将A指针向后移动一位，指向下一个节点。否则，A已经遍历到链表headA的末尾，将A指针重新指向headB的头节点。
    （2.2）如果B不为空，将B指针向后移动一位，指向下一个节点。否则，B已经遍历到链表headB的末尾，将B指针重新指向headA的头节点。
    3.当A和B相等时，表示找到了交点或者两个链表都遍历完毕（没有交点）。返回A指针即可。

    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA;
        ListNode B = headB;

        while (A != B){
        if (A != null){
            A = A.next;
        }else{
            A = headB;
        }
        if (B != null){
            B = B.next;
        }else{
            B = headA;
        }
    }
        return A;
    }
}
    0 赞同 0 条回复
  • Sexypig. 普通 2023年6月19日 下午10:53

    代码：

    class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        node1, node2 = headA, headB

        while node1 != node2:
            node1 = node1.next if node1 else headB
            node2 = node2.next if node2 else headA

        return node1
    0 赞同 0 条回复
  • 伏月三十 普通 2023年6月19日 下午10:27

    这道看解析了啊啊啊啊
    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //定义两个头节点
    ListNode p1=headA;
    ListNode p2=headB;
    if(p1null || p2null){
    return null;
    }

        while(p1!=p2){
        if(p1==null){
            p1=headB;
        }else{
            p1=p1.next;
        }

        if(p2==null){
            p2=headA;
        }else{
            p2=p2.next;
        }
    }
    //没有公共节点相遇为null
    return p1;
}

    }

    0 赞同 0 条回复
  • 江畅 普通 2023年6月19日 下午10:25

    “`c++
    class Solution {
    public:
    // 双指针
    // 时间复杂度 O(N + M)，两个链表节点数和
    // 空间复杂度 O(1)
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if (headA == nullptr || headB == nullptr) { return nullptr; }
    ListNode* pA = headA;
    ListNode* pB = headB;
    while (pA != pB) {
    pA = (pA == nullptr ? headB : pA->next);
    pB = (pB == nullptr ? headA : pB->next);
    }
    return pA;
    }
    };
    “`

    0 赞同 0 条回复
  • mpweixin用户 永久会员 2023年6月19日 下午10:24 
    //注意要使用辅助指针，保持原链表不变
ListNode getIntersectionNode(ListNode headA, ListNode headB) {

    ListNode curA = headA;
    ListNode curB = headB;

    while(curA != curB){
        curA = curA == null?headB:curA.next;
        curB = curB == null?headA:curB.next;
    }

    return curA;
}
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月19日 下午10:16

    思想：先计算两条链表的长度，计算其长度的差lenA-lenB=k，设置快指针在较长链表，慢指针在较短链表，快指针先行k步，然后快慢指针共同前进，遇到相等结点则返回公共节点；若未遇到公共节点，则返回null
    时间复杂度:O(m+n) 空间复杂度:O(1)

    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a=headA, b=headB;
        int lenA=0, lenB=0;
        while(a!=null){
            lenA++;
            a=a.next;
        }
        while(b!=null){
            lenB++;
            b=b.next;
        }

        ListNode p, q;//p为快指针，q为慢指针
        int flag=0; //标志位，0表示A更长（或相等），1表示B更长
        if(lenA>=lenB){
            p=headA;
            q=headB;
            flag=0;
        }else{
            p=headB;
            q=headA;
            flag=1;
        }

        int cnt=0, k=0;
        if(flag==0){
            k=lenA-lenB;
        }else{
            k=lenB-lenA;
        }

        while(cnt
    0 赞同 0 条回复
  • désire. 普通 2023年6月19日 下午10:02

    C++实现
    class Solution {
    public:
    ListNode getIntersectionNode(ListNode *headA, ListNode *headB) {
    if(headA NULL) return NULL;
    if(headB     NULL) return NULL;
    ListNode     curA = headA;
    ListNode* curB = headB;
    int lenA = 0 , lenB = 0;
    while(curA){
    lenA++;
    curA = curA->next;
    }
    while(curB){
    lenB++;
    curB = curB->next;
    }
    curA = headA;
    curB = headB;
    if(lenB > lenA){
    swap(lenA,lenB);
    swap(curA,curB);
    }
    int gap = lenA – lenB;
    while(gap–){
    curA = curA->next;
    }
    while(curA != NULL){
    if(curA curB)
    return curA;
    curA = curA->next;
    curB = curB->next;
    }
    return NULL;
    }
    };

    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月19日 下午9:59

    C++
    class Solution {
    public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *a = headA;
    ListNode *b = headB;
    while(a != b){
    a = a != NULL ? a->next : headB;
    b = b != NULL ? b->next : headA;
    }
    return a;
    }
    };
    时间复杂度为O(n);
    空间复杂度为O(1);
    思想：
    虽然两个链表的长度可能不相同，但是二者的总长度是相同的，如果定义的两个遍历链表的指针相遇了，那么则是交点。

    0 赞同 0 条回复
  • peach 普通 2023年6月19日 下午9:59

    思路

    • 求两个链表的相交节点，我们可以先让两个链表尾部对齐，然后长的链表先走长度差步数，然后一起走，节点重合就找到了第一个公共节点
    • 先给方法求两个链表的长度，假设A长，如果A短就交换
    • 然后按照逻辑撰写代码即可

    代码

    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = getLength(headA);
        int lenB = getLength(headB);
        if(lenA < lenB){ //这一步保证链表A更长
            int temp = lenA;
            lenA = lenB;
            lenB = temp;
            ListNode tempNode = headA;
            headA = headB;
            headB = tempNode;
        }
        int gap = lenA - lenB; //计算长度差
        while(gap-- > 0){ //这个循环让两个链表的尾部对齐，就是让headA先走gap步
            headA = headA.next;
        }
        while(headA != null){ //然后两个指针一起走，走到找到相交节点位置
            if(headA == headB) return headA;
            else {
                headA = headA.next;
                headB = headB.next;
            }
        }
        return null; //全部走完还没有相交，返回null
    }
    private int getLength(ListNode head){ //给出一个方法，返回链表的长度
        int res = 0;
        while(head != null){
            res++;
            head = head.next;
        }
        return res;
    }
}
    0 赞同 0 条回复
  • ～ 普通 2023年6月19日 下午9:57

    c++代码
    class Solution {
    public:
    ListNode getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode     p1 = headA, *p2 = headB;
    while(p1!=p2){
    if(p1!=nullptr) p1 = p1->next;
    else p1 = headB;
    if(p2!=nullptr) p2 = p2->next;
    else p2 = headA;
    }
    return p1;
    }
    };

    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月19日 下午9:56 
    class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int len1=0,len2=0;
        ListNode *p1=headA,*p2=headB;
        while(p1!=nullptr)
        {
            p1=p1->next;
            len1++;
        }
        while(p2!=nullptr)
        {
            p2=p2->next;
            len2++;
        }
        p1=headA,p2=headB;
        if(len1>len2)
        {
            swap(p1,p2);
            swap(len1,len2);
        }
        while(len1!=len2)
        {
            p2=p2->next;
            len2--;
        }
        while(p1!=nullptr)
        {
            if(p1==p2)
            {
                break;
            }
            else
            {
                p1=p1->next;
                p2=p2->next;
            }
        }
        return p1;
    }
};

    时间复杂度：O(n)，空间复杂度：O(1)。

    0 赞同 0 条回复
  • Dsjh 普通 2023年6月19日 下午9:51

    “`c++
    // c++实现
    /**
    * Definition for singly-linked list.
    * struct ListNode {
    * int val;
    * ListNode *next;
    * ListNode(int x) : val(x), next(NULL) {}
    * };
    */
    class Solution {
    public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if(!headA || ! headB)
    return nullptr;
    ListNode* cur1 = headA;
    ListNode* cur2 = headB;
    while(cur1 != cur2){
    // 设 a 链从头结点到相交节点的距离为 a
    // b 链从头节点到相交节点的距离为 b
    // 相交节点到终点的距离为 c
    // l1 : a+c+b
    // l2 : b+c+a
    // 相当于在两条链表尾部加了一个 null 节点，
    // 则可能有两个相交节点
    // 1 有两个相交节点，即null之前有一个，
    // 2 有一个即null节点，那么找到的是 null 节点
    cur1 = cur1 ? cur1->next : headB;
    cur2 = cur2 ? cur2->next : headA;
    }
    return cur1;
    }
    };

    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月19日 下午9:48

    C++实现

    “`C++
    class Solution {
    public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *a=headA,*b=headB;
    while(a!=b){
    a=a==NULL?headB:a->next;
    b=b==NULL?headA:b->next;
    }
    return a;
    }
    };
    “`

    0 赞同 0 条回复
  • 小吕 普通 2023年6月19日 下午9:45

    c++实现
    ListNode* lA = headA;
    ListNode* lB = headB;
    int len1 =0,len2=0;
    while(lA!=NULL)
    {len1++;
    lA = lA->next;

        } 
    while(lB!=NULL)
    {len2++;
        lB = lB->next;

    }
    lA = headA;
    lB = headB;
    if(len1<len2)
    {
        swap(lA,lB);
        swap(len1,len2);
    }
    int lencha = len1-len2;
    while(lencha--)
    {
        lA= lA->next;
    }
    while(lB!=NULL)
    {
        if(lA==lB)
        {
            return lA;
        }
        lA=lA->next;
        lB = lB->next;
    }
    return NULL;
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月19日 下午9:44

    java实现

      ListNode A=headA;
        ListNode B=headB;
        if(headA==null||headB==null)return null;
        // while(A!=B){
        //     A=A==null?headB:A.next;
        //     B=B==null?headA:B.next;
        // }
        // return A;
        int lenga=0;
        int lengb=0;
        while(A!=null){
            lenga++;
            A=A.next;
        }
         while(B!=null){
            lengb++;
            B=B.next;
        }
        A=headA;
        B=headB;
        int result=lenga-lengb;
        if(result>=0){
               for(int i=0;i<result;i++){
                   A=A.next;
               } 
        }else{
            result=-result;
             for(int i=0;i<result;i++){
                   B=B.next;
               } 
        }
       while(A!=B){
        A=A.next;
        B=B.next;
       }
    return A;

    }

    时间复杂度为n1+n2，空间复杂度为1。按照帅地的思路。写了两种方法

    0 赞同 0 条回复
  • * 普通 2023年6月19日 下午9:39

    c实现
    struct ListNode getIntersectionNode(struct ListNode headA, struct ListNode headB)
    {    struct ListNode     node1 = headA, *node2 = headB;    
    while (node1 != node2)    
    {        if (node1)            
    node1 = node1->next;        
    else            
    node1 = headB;        
    if (node2)            
    node2 = node2->next;
            else
                node2 = headA;
        }
        return node1;
    }

    0 赞同 0 条回复
  • 悠若 普通 2023年6月19日 下午9:37 
    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

    时间复杂度：O(m+n)，空间复杂度：O(1)。

    0 赞同 0 条回复
  • 雨落圆荷 普通 2023年6月19日 下午9:28

    class Solution{
    ListNode getIntersectionNode(ListNode headA，ListNode headB)｛
    if（headAnull）return null;
    ListNodeA=headA；
    ListNodeB=headB;
    while(A!=B){
    A=A    null ?headB:A.next;
    B=Bnull ?headA:B.next;

    }
    return A;

    ｝
    }
    时间复杂度:O(n+m)
    空间复杂度：O(1)

    0 赞同 0 条回复
  • Ming 普通 2023年6月19日 下午9:16

    这里是Ming打卡：
    这里与增删改无关，不需要虚拟头结点
    注意循环终止的条件是他们相等（毕竟题目就是求这个）
    如果相遇两个结点会走的长度=a+b+n，n为公共部分，如果不相遇会走a+b更长了

    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //设公共长度为n，a部分长度为a，b部分长度为b
        //如果相遇画个简图可知：a走的长度=a+n+b b的长度=b+n+a
        //总结：a与b的第一个公共结点就是相遇点
        if(headA == null || headB == null) return null;
        ListNode a = headA;
        ListNode b = headB;
        while(a != b) {
            //a走完就走b的路，b走完就走a的路
            a = a==null? headB : a.next;
            b = b==null? headA : b.next;
            //如果不相遇：他们会都走向null，且长度都是相等
            if(a == null && b == null) return null;
        }
        //此时a与b相等，随便返回一个;
        return a;
    }
}
    0 赞同 0 条回复
  • Vow the vow。 普通 2023年6月19日 下午8:52

    两个指针都遍历一遍两个链表，分别为A+B和B+A。

    class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;
        while(p1 != p2){
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA: p2.next;
        }
        return p1;
    }
}
    0 赞同 0 条回复
  • 行动派小彩笔 普通 2023年6月19日 下午8:52

    /**
    * Definition for singly-linked list.
    * struct ListNode {
    * int val;
    * ListNode next;
    * ListNode(int x) : val(x), next(NULL) {}
    * };
    */
    // 利用两个链表相加路径相同来解决
    // 时间复杂度O(m+n); 两个链表长度和
    // 空间复杂度O(1)；没有辅助空间
    class Solution {
    public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *A = headA,    B = headB;
    while(A!=B)
    {
    A = ANULL?headB:A->next;
    B = B    NULL?headA:B->next;
    }
    return A;
    }
    };

    1 赞同 0 条回复

# 回答此问题

后才能回答