泽阳普通 2024年12月25日下午6:41

另一个思路

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Map<Integer, ListNode> bMap = new HashMap<>();
        while (headB != null) {
            bMap.put(headB.val, headB);
            headB = headB.next;
        }
        while (headA != null) {
            if (bMap.containsKey(headA.val)) {
                return headA;
            }
            headA = headA.next;
        }
        return null;
    }
}

0 赞同 0 条回复

為愛而生普通 2024年12月20日下午4:06

时间复杂度O(N) 空间O(1)
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode l1 = headA;
ListNode l2 = headB;
while (l1 != l2) {
l1 = (l1 null) ? headB : l1.next;
l2 = (l2 null) ? headA : l2.next;
}
return l1;
}
}

0 赞同 0 条回复

宇晴普通 2024年12月3日下午9:03

双指针遍历

var getIntersectionNode = function(headA, headB) {
    let a = headA, b = headB;
    while(a != b) {
        a = a != null ? a.next : headB;
        b = b != null ? b.next : headA;
    }
    return a;
};

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日上午1:50

/**
解题思路:
设A链表不相交部分长度为x, B链表不相交部分长度为y，相交部分长度为z
A链表遍历结束总长度为x+z
B链表遍历结束总长度为y+z
A遍历结束在切换到B遍历y长度后总距离为x+z + y
B遍历结束在切换到A遍历x长度后总距离为y+z + x, 两距离相等，正好停留在相交位置
如果两链表不相交，则最终都会停留在空节点

复杂度分析：
遍历总长度为两链表不相交部分+相交部分的和，复杂度O(N)
 */
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode p = headA;
        ListNode q = headB;

        while (p != q){
            if (p == null){
                p = headB;
            } else{
                p = p.next;
            }

            if (q == null){
                q = headA;
            } else{
                q = q.next;
            }
        }

        return q;

    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年11月28日下午10:27

双指针，有两个相交点，那必然两个指针的路程是一致的，交换一下即可

# 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 条回复

桃桃摇摇奶昔° 普通 2024年11月27日上午11:56

/**
 * 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;

    }
}

时间复杂度O（N）
空间复杂度O（1）

0 赞同 0 条回复

Lil Lee_ 普通 2024年11月26日下午11:06

//暴力循环
/**
 * 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) {
        for(ListNode A = headA;A != null; A = A.next){
            for(ListNode B = headB;B != null; B = B.next)
                if(A == B) return A;
        }
        return null;
    }
}

0 赞同 0 条回复

ㅤ牛马学编程普通 2024年11月26日上午12:18

“`java
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
// 如果A/B为空,直接返回空
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;

}

}
时间复杂度:o(a+b)
空间复杂度:o(1)

0 赞同 0 条回复

树懒在橘子洲数星星普通 2024年11月25日下午6:51

“`python
class Solution(object):
def getIntersectionNode(self, headA, headB):
a=headA
b=headB
//当它们相遇时，所指向的结点就是第一个公共结点
while a!=b:
a=a.next if a else headB
b=b.next if b else headA
return a
时间复杂度：O(M+N) M、N为链表l1和l2的长度
空间复杂度：O(1)

0 赞同 0 条回复

yelinliner 普通 2024年11月24日下午6:09

###

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 非空判断
        if (headA == null || headA == null)
            return null;
        ListNode A = headA;
        ListNode B = headB;
        // A==B时 要么相遇；要么就是两个都走完了（走到了null）也没有相遇
        while (A != B) {
            A = A == null ? headB : A.next;
            B = B == null ? headA : B.next;
        }
        return A;
    }
}

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

0 赞同 0 条回复

LovLe 普通 2024年11月23日下午10:40

考虑构建两个节点指针 A , B 分别指向两链表头节点 headA , headB ，做如下操作：

指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：a+(b−c)
指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：b+(a−c)
如下式所示，此时指针 A , B 重合，并有两种情况：a+(b−c)=b+(a−c)
- 若两链表有公共尾部 (即 c>0 ) ：指针 A , B 同时指向「第一个公共节点」node 。
- 若两链表无公共尾部 (即 c=0 ) ：指针 A , B 同时指向 null 。
  因此返回 A 即可。

# 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:
        A,B=headA,headB
        while A!=B: #如果没有公共节点，那么两个指针交换跑道，最后都遍历到None，然后相等退出
            A=A.next if A else headB    # 如果A遍历完了，则到B上继续遍历
            B=B.next if B else headA    # 如果B遍历完了，则到A上继续遍历
        return A    #返回共同的节点，首次相遇的节点；巧妙的是，他们会同时相遇这个节点（相同的步长step=1，相同的长度distance=a+b-c）

时间复杂度：O(n+m-c)

空间复杂度：O(1)

引用一个题解的观点：

如果两链表的长度相等，只要从头开始查找到第一个相同节点就行啦，所以关键问题是解决两链表的长度不相等问题：（1）第一种方法是先统计出两链表的长度n1和n2，则只要让较长的链表指针先走n1-n2（假设n1>n2）步，之后同时出发即可（2）第二种方法就是像这里的交换跑道，因为长度之和n1+n2是不变的，第一遍遍历到尾部时，再跑到另一个链表的头部，再从这个链表头部遍历，此时两指针到达尾部的距离就相等了。A = A.next if A else headB 而非 A = A.next if A.next else headB 相当于在链表尾部增设一个null节点，如果链表无相交节点，最后就遍历到null返回即可，无需单独考虑这种情况

针对方法一，先同步起点，先有个快指针走到diff=abs(na-nb)，然后同步走，相遇的点就是共同点。该方法缺点是需要先完整遍历A,B，得到两个链表的长度，然后再遍历到共同点。

# 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:
        na,nb=0,0
        a,b=headA,headB #获取两个链表的长度
        while a:
            a=a.next
            na+=1
        while b:
            b=b.next
            nb+=1

        diff=na-nb if na>nb else nb-na
        A,B=headA,headB #走个diff长度节点
        if na>nb:
            diff=na-nb
            while diff:
                A=A.next
                diff-=1
        elif na<nb:
            diff=nb-na
            while diff:
                B=B.next
                diff-=1
        while A!=B: #屏蔽了不同长度，共同出发，相遇点为共同点
            A=A.next
            B=B.next
        return A

0 赞同 0 条回复

无言永久会员 2024年11月23日下午6:13

/**
 * 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* nodeA = headA;
        ListNode* nodeB = headB;
        int m = 0, n = 0;
        while(nodeA != nodeB) {
            if(nodeA->next == nullptr && nodeB->next == nullptr) {
                //没有交点的情况
                return nullptr;
            } else if(nodeA->next == nullptr) {
                nodeA = headB;
                nodeB = nodeB->next;
            } else if(nodeB->next == nullptr) {
                nodeB = headA;
                nodeA = nodeA->next; 
            } else {
                nodeA = nodeA->next; 
                nodeB = nodeB->next;
            }
        }
        return nodeA;
    }
};
时间复杂度: O(m+n) m 和 n 分别是链表 headA 和 headB 的长度
空间复杂度: O(1)

0 赞同 0 条回复

捕风永久会员 2024年11月22日下午10:46

时间复杂度：O(a+b)，a和b分别为两个链表的长度
空间复杂度：O(1)

/**
 * 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和B是否走完了来时的路，如果走完了就让其走对方的路,没走完就继续指向下一个节点
            A = A == null ? headB : A.next;
            B = B == null ? headA : B.next;
        }  // 相等，即交点时会跳循环

        // 返回交点的值
        return A;

    }
}

0 赞同 0 条回复

biangbb 普通 2024年11月22日下午10:00

class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode f1=headA;
ListNode f2=headB;
while(f1!=f2){
//两条链表最后都指向了同一个 null （None）节点，代替了不相交的特殊情况。
//f1null 而不是 f1.nextnull
if(f1null){
f1=headB;
}else{
f1=f1.next;
}
if(f2null){
f2=headA;
}else{
f2=f2.next;
}
}
return f1;
}
}

0 赞同 0 条回复

岱永久会员 2024年11月22日下午9:45

set去重

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        while(headA != null){
            set.add(headA);
            headA = headA.next;
        }
        while(headB != null && !set.contains(headB)){
            headB = headB.next;
        }
        return headB;

    }
}

0 赞同 0 条回复

土豆哥普通 2024年11月22日上午12:24

“`java
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p = headA;
ListNode q = headB;
while(p!=q)
{
if(p!=null) p = p.next;
else p = headB;

        if(q!=null) q = q.next;
        else q = headA;
    }
    return p;

}

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

0 赞同 0 条回复

Poetry and distance 永久会员 2024年11月22日上午12:10

思路：双指针通过交替遍历相遇找到公共节点，如果有一个链表为空，则没有公共节点
/**
 * 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,B=headB;
        while(A!=B){
            A=A!=null?A.next:headB;
            B=B!=null?B.next:headA;
        }
        return A;
    }
}
时间复杂度：O(m+n),m，n表示链表长度
空间复杂度：O(1)

0 赞同 0 条回复

爱姆露普通 2024年11月21日下午10:41

ListNode * A = headA;
ListNode * B = headB;
while(A!= B)
{
A = A != nullptr? A->next:headB;
B = B != nullptr? B->next:headA;
}
return A;
时间复杂度：O(1), 空间复杂度：O(1)

0 赞同 0 条回复

橙子陈爱吃橙子普通 2024年11月21日下午8:02

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

        ListNode listA = headA;
        ListNode listB = headB;

        while (listA != listB) {
            listA = (listA == null) ? headB : listA.next;
            listB = (listB == null) ? headA : listB.next;
        }

        return listA;
    }
}

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

0 赞同 0 条回复

zing 普通 2024年11月21日下午3:05

优雅

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

        while index1 != index2:
            index1 = index1.next if index1 else headB
            index2 = index2.next if index2 else headA
        return index1

0 赞同 0 条回复

mpweixin用户普通 2024年11月21日下午2:29

解题思路：

我们可以使用两个指针l1和l2分别从两个链表的头部开始遍历。当某个指针到达链表末尾时，我们让它从另一个链表的头部重新开始。这样，当两个指针相遇时，就找到了第一个相交节点。这个方法之所以有效，是因为两个指针走过的总路程是相等的：链表A的长度 + 链表B的非公共部分 = 链表B的长度 + 链表A的非公共部分。所以如果有相交点，两个指针一定会在相交点相遇。如果没有相交点，两个指针最终都会变为nullptr。

时空分析：

时间复杂度：O(n)，其中n是两个链表的长度之和。每个指针最多遍历两个链表各一次。

空间复杂度：O(1)，只使用了两个指针变量。

代码实现：

“`C++
class Solution {
public:
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
// 初始化两个指针分别指向两个链表头部
ListNode* l1 = headA;
ListNode* l2 = headB;

    // 当两个指针不相等时继续遍历
    while (l1 != l2) {
        // 如果某个指针到达末尾，则转向另一个链表的头部
        // 否则继续在当前链表遍历
        l1 = l1 == nullptr ? headB : l1->next;
        l2 = l2 == nullptr ? headA : l2->next;
    }
    return l1;  // 返回相交点或nullptr
}

};

“`

0 赞同 0 条回复

Renasc 普通 2024年11月21日下午1:41

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

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 如果有一个为null，就返回null
        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 条回复

Pendulumpal 普通 2024年11月21日下午12:22

用集合记录headA链表所有节点的地址
遍历headB,找到其中第一个存在于st的地址返回
T O(n), M O(m),m为headA链表长度

“`c++
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_set st;
while(headA){
st.insert(headA);
headA=headA->next;
}
while(headB){
if(st.count(headB)){
return headB;
}
headB=headB->next;
}
return nullptr;
}
“`

0 赞同 0 条回复

Tom Yuan 普通 2024年11月21日下午12:14

从各自的起点出发寻找相同的节点如果有任意一个走完了还找不到就指向第二个继续找直到二者全部走完
有一种构造了环的感觉但实际上又不是环在某个时间节点将两个链表连接了起来

# 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 headA == None or headB == None:
            return None

        a = headA
        b = headB
        while a != b:
            # connect back to the other LL
            # if reached anyone's end but still didn't find.
            a = a.next if a else headB
            b = b.next if b else headA

        return a

time: O(m+n)
space: O(1)

0 赞同 0 条回复

Rad 普通 2024年11月21日上午11:15

时间复杂度O（m+n）
空间复杂度O1
/**
* 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 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 条回复

jaron 普通 2024年11月21日上午10:29

时间复杂度：O(n+m)，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){
            // 走到null就回到另一个链表开头
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年11月21日上午10:03

“`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 == nullptr || headB == nullptr) return nullptr;
ListNode* n1 = headA;
ListNode* n2 = headB;
while(n1!=n2){
if(n1!=nullptr){
n1 = n1->next;
}else{
n1 = headB;
}
if(n2!=nullptr){
n2 = n2->next;
}else{
n2 = headA;
}
}
return n1;
}
};
“`
打卡

0 赞同 0 条回复

🌟 普通 2024年11月21日上午9:15

好
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;
if(AB) return A;
}
return nullptr;

};

0 赞同 0 条回复

咕普通 2024年11月21日上午12:00

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        A, B = headA, headB
        while A != B:
            A = A.next if A else headB
            B = B.next if B else headA
        return A

时间O(n)空间O(1)

0 赞同 0 条回复

陆狗陆狗普通 2024年11月20日下午11:55

题解

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA==null || headB==null){
            return null;
        }
        ListNode nodeA=headA;
        ListNode nodeB=headB;
        while(nodeA!=nodeB){
        // 【错误点1】
            nodeA = nodeA==null?headB:nodeA.next;
            nodeB=  nodeB==null?headA:nodeB.next;
        }
        return nodeA;
    }
}

错误点1 ：为什么 nodeA = nodeA.nextnull?headB:nodeA.next; 不是去判断next是不是null而是去判断 nodeAnull？因为2个链表不一定相交，会导致死循环。但是如果循环把null作为一个节点，就永远有个null的交点，就不会死循环了。

1 赞同 0 条回复

Kisara 普通 2024年11月20日下午11:27

“java
双指针同时遍历，有交点时，走到底后移到另一个头部节点，一定会在第二次遍历中相遇，若无交点，p1=p2=null，最后跳出循环返回null

/**
* 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 p1=headA;
        ListNode p2=headB;

    while(p1!=p2){
        p1=p1==null?headB:p1.next;
        p2=p2==null?headA:p2.next;
    }

    return p1;
}

}

O(n) O(1)

0 赞同 0 条回复

遇事不决睡大觉普通 2024年11月20日下午11:12

“`java
class Solution {
public 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 条回复

越努力越幸运普通 2024年11月20日下午11:11

“`c++
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(m+n) m和n分别表示两个链表的长度
空间复杂度：O(1)

“`

0 赞同 0 条回复

lQl 永久会员 2024年11月20日下午11:05

双指针:

class Solution {
    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;
    }
}

0 赞同 0 条回复

张君雅小妹妹普通 2024年11月20日下午10:53

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tmpA = headA;
        ListNode tmpB = headB;
        while(tmpA != null && tmpB != null){
            if(tmpA == tmpB) return tmpA;
            tmpA = tmpA.next;
            tmpB = tmpB.next;
        }
        if(tmpA != null){
            int cnt = getDif(tmpA);
            return compare(headA, headB, cnt);
        }

        if(tmpB != null){
            int cnt = getDif(tmpB);
            return compare(headB, headA, cnt);
        }

        return null;
    }

    int getDif(ListNode tmp){
        int cnt = 0;
        while(tmp != null){
            tmp = tmp.next;
            cnt++;
        }
        return cnt;
    }

    ListNode compare(ListNode fast, ListNode slow, int cnt){
        while(cnt > 0){
            fast = fast.next;
            cnt--;
        }
        while(fast != null){
            if(fast == slow){
                return fast;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return null;
    }
}

时间复杂度 o(n)，空间复杂度 o(1)

0 赞同 0 条回复

时光烙印普通 2024年11月20日下午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 条回复

Firefly 普通 2024年11月20日下午10:44

/**
* 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) {
auto pA=headA,pB=headB;
while(pA!=nullptr&&pB!=nullptr)
{
pA=pA->next,pB=pB->next;
}

    if(pA!=nullptr)    
    {  
        auto pTmp=pA;
        pA=headA,pB=headB;
        while(pTmp!=nullptr)
        {
            pTmp=pTmp->next;
            pA=pA->next;
        }
    }
    else if(pB!=nullptr)   
    {
        auto pTmp=pB;
        pA=headA,pB=headB;
        while(pTmp!=nullptr)
        {
            pTmp=pTmp->next;
            pB=pB->next;
        }
    }
    else
    {
        pA=headA,pB=headB;
    }

    while(pA!=nullptr&&pB!=nullptr)
    {
        if(pA->val==pB->val)
           return pA;
        pA=pA->next,pB=pB->next;   
    }
    return nullptr;
}

};时间复杂度 o(n)，空间复杂度 o(1)

0 赞同 0 条回复

晓宇普通 2024年11月20日下午10:43

/**
* 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 *p = headA, *q = headB;
while(p != q){
p = p nullptr ? headB : p->next;
q = q nullptr ? headA : q->next;
}
return p;
}
};
时间复杂度 o(m + n)，空间复杂度 o(1)
思路：成环互补逆搜索，相交为对称中心

0 赞同 0 条回复

生活在经验里普通 2024年11月20日下午10:35

“`golang
// 节点相交和节点值相等不是一回事
// 节点相交: 指的是两个链表在某个节点开始共享同一个内存地址
func getIntersectionNode(headA, headB *ListNode) *ListNode {
if headA == nil {
return nil
}
if headB == nil {
return nil
}

tmpA := headA
tmpB := headB
for tmpA!=tmpB{
    if tmpA == tmpB {
        return tmpA
    }
    if tmpA == nil {
        tmpA = headB
        continue
    }
    if tmpB == nil {
        tmpB = headA
        continue
    }
    tmpA = tmpA.Next
    tmpB = tmpB.Next
}

}

0 赞同 0 条回复

. 普通 2024年11月20日下午10:07

我用的时间好长，是因为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) {
        ListNode nodeA = headA;
        ListNode nodeB = headB;
        if(nodeA == null||nodeB == null) return null;
        while(nodeA != nodeB){
            nodeA = nodeA == null? headA : nodeA.next;
            nodeB = nodeB == null? headB : nodeB.next;
        }
        return nodeA;
    }
}

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

0 赞同 0 条回复

mpweixin用户普通 2024年11月20日下午10:01

a.思路分析
1.定义两个探索的指针
2.由于A+B的路径对于B+A的路径和，如果遇到一个链表走完了可以指向下一个链表头节点

b.代码：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;

        while(curA!=curB)
        {
            curA = curA ? curA->next : headB;
            curB = curB ? curB->next : headA;
        }
        return curA;
    }
};

c.时间复杂度：o(m+n)，m和n分别是链表a和b的长度；空间复杂度o(1),使用了常数级的额外空间。

0 赞同 0 条回复

mpweixin用户普通 2024年11月20日下午9:54

class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int l1 = 0, l2 = 0;
ListNode * temp = headA;
while(temp){
l1++;
temp=temp->next;
}
temp = headB;
while(temp){
l2++;
temp=temp->next;
}
if(l1 != l2){
int t = abs(l1-l2);
if(l1>l2){
while(t!=0){
headA = headA->next;
t–;
}
}
else{
while(t!=0){
headB = headB->next;
t–;
}
}
}
while(headA && headB){
if(headA headB){
return headA;
}
else{
headA = headA->next;
headB = headB->next;
}
}
return NULL;
}
};
思路：先遍历一遍两个链表求出各自的长度，根据长度差调整较长链表的起点，使两个链表一样长，这时同时开始遍历，如果相交直接返回对应节点，如果全都遍历到结尾证明两者不想交。
时间复杂度O(n)，空间复杂度O(0)。

0 赞同 0 条回复

黑键〰普通 2024年11月20日下午9:41

/**
* 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) {
let a = headA
let 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
};

思路：循环完自身后循环另一个链表，有重合点则会相遇，否则都为null时才相等
时间复杂度O(N)
空间复杂度O(1)

0 赞同 0 条回复

momo 普通 2024年11月20日下午9:31

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:
cur_a = headA
cur_b = headB
while(cur_a != cur_b):
if cur_a:
cur_a = cur_a.next
else:
cur_a = headB
if cur_b:
cur_b = cur_b.next
else:
cur_b = headA
return cur_a

时间复杂度O(n)
空间复杂度O(1)
思路就是双指针，通过经过其中一条链到结尾接入另一条链，最后的交点两者路程相同，就是公共点

0 赞同 0 条回复

月下足迹普通 2024年11月20日下午9:16

/**
* 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 pA = headA;
    ListNode pB = headB;

    //遍历两个链表
    while(pA != pB) {
        if (pA == null) {
            pA = headB;
        }else {
            pA = pA.next;
        }

        if (pB == null) {
            pB = headA;
        }else {
            pB = pB.next;
        }

    }

    return pA;
}

}

0 赞同 0 条回复

Jerry 普通 2024年11月20日下午9:06

class Solution {
public:
    int getSize(ListNode* head){
        int len = 0;
        while(head){
            len++;
            head = head->next;
        }
        return len;
    }
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = getSize(headA);
        int lenB = getSize(headB);
        int gap;
        ListNode* longer;
        ListNode* shorter;
        if(lenA > lenB){
            longer = headA;
            shorter = headB;
            gap = lenA - lenB;
        }
        else{
            longer = headB;
            shorter = headA;
            gap = lenB - lenA;
        }
        for(int i = 0; i < gap && longer; i++){
            longer = longer->next;
        }
        while(longer && shorter){
            if(longer == shorter){
                return longer;
            }
            longer = longer->next;
            shorter = shorter->next;
        }
        return NULL;
    }
};

时间o(n)
空间o(1)

0 赞同 0 条回复

Carry on 普通 2024年11月20日下午9:00

class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA null || headB null) {
return null; // 如果任意一个链表为空，直接返回 null
}

    // 定义两个指针
    ListNode pointerA = headA;
    ListNode pointerB = headB;

    // 两个指针交替遍历两个链表
    while (pointerA != pointerB) {
        // 如果 pointerA 到达末尾，则转到链表 B 的头节点
        pointerA = (pointerA == null) ? headB : pointerA.next;
        // 如果 pointerB 到达末尾，则转到链表 A 的头节点
        pointerB = (pointerB == null) ? headA : pointerB.next;
    }

    // 返回交点（如果没有交点，则返回 null）
    return pointerA;
}

}

0 赞同 0 条回复

parsons 普通 2024年11月20日下午8:59

class Solution {
public:
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
// 1.创建左右节点
ListNode* A = headA;
ListNode* B = headB;
// 2.A走完整个headA链表，走到headB然后遍历到结束或者相遇
// B走完整个headB链表，走到headA然后遍历到结束或者相遇
while (A != B) {

        if (A != nullptr) {
            A = A->next;
        } else {
            A = headB;
        }

        if (B != nullptr) {
            B = B->next;
        } else {
            B = headA;
        }
    }
    //3.返回节点
    return A;
}

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

0 赞同 0 条回复

hjx 普通 2024年11月20日下午8:59

class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1=headA,p2=headB;
while(p1!=p2){
p1=(p1!=null)?p1.next:headB;
p2=(p2!=null)?p2.next:headA;
}
return p1;
}
}
时间O(N)，空间O（1）

0 赞同 0 条回复

Xiang. 永久会员 2024年11月20日下午8:50

/**
* 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(headAnull||headBnull) return null;
ListNode tmpA=headA;
ListNode tmpB=headB;
while(tmpA!=tmpB){
if(tmpAnull) tmpA=headB;
else tmpA=tmpA.next;
if(tmpBnull) tmpB=headA;
else tmpB=tmpB.next;
}
return tmpA;
}
}
思路：先判空，如果有至少一个链表为空，则直接返回null，当都不为空时使用双指针交叉遍历即可得到最终解。
时间复杂度O(n+m)
空间复杂度O(1)

0 赞同 0 条回复

苯庸普通 2024年11月20日下午8:25

class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode l1 = headA, l2 = headB;
while(l1 != l2){
l1 = l1 != null ? l1.next : headB;
l2 = l2 != null ? l2.next : headA;
}
return l1;
}
}
时间：o（n）
空间：o（1）

0 赞同 0 条回复

迢迢星野普通 2024年11月20日下午8:24

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

        return pA;        
    }
}

本题相当于是在求链表相交时的节点，定义两个指针 pA 和 pB 分别指向链表 headA 和 headB 的头节点，用于遍历两个链表，直至 pA == pB。在循环中，如果 pA 或 pB 达到链表末尾（即其值等于 null）时，则将其重定向到另一个链表的头节点，这样就可以保证遍历两个指针可以同时达到相交节点。当 pA == pB 时，退出循环，返回相交节点。如果没有相交节点，返回 null。

时间复杂度：O(m + n)，需要遍历两个链表。
空间复杂度：O(1)，使用了常数级的额外空间。

0 赞同 0 条回复

WYX 普通 2024年11月20日下午8:18

LCR 140. 训练计划 II(https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/)
时间复杂度 O(n)
class Solution { public ListNode deleteNode(ListNode head, int val) { ListNode current = new ListNode(-1, head); ListNode newHead = current; while(current != null){
if(current.next.val == val){ current.next = current.next.next;
break; }
current = current.next; }
return newHead.next; }
} LCR 140. 训练计划 II(https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/) 思路：快慢指针时间复杂度 O(n) class Solution {
public ListNode trainingPlan(ListNode head, int cnt) { // 双指针两指针相差 cnt
ListNode first = head; ListNode second = head;
// second 向后 cnt 位
for(int i = 0; i < cnt; i ++){ second = second.next;
}
while(second != null){ // second 指向null时 first 指向倒数第cnt个
second = second.next; first = first.next;
}
return first; }
} LCR 142. 训练计划 IV(https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/) 时间复杂度 O(n) class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) { ListNode ans = new ListNode(-1, null);
ListNode ans_head = ans; ListNode l1_temp = l1;
ListNode l2_temp = l2;
while(l1_temp != null && l2_temp != null){ if(l1_temp.val < l2_temp.val){
ans.next = l1_temp; l1_temp = l1_temp.next;
ans = ans.next; }else{
ans.next = l2_temp; l2_temp = l2_temp.next;
ans = ans.next; }
}
if(l1_temp != null){ // 将剩余部分接到后续
ans.next = l1_temp; }
if(l2_temp != null){
// 将剩余部分接到后续 ans.next = l2_temp;
}
return ans_head.next; }
} LCR 171. 训练计划 V(https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/) 时间复杂度 O(n) class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) { // 若存在公共链则从最后到第一个公共部分长度相同
// 首先将 A B 对齐 // 统计链表长度
int lenA = getLen(headA); int lenB = getLen(headB);
if(lenA > lenB){
// A 较长 A 首先向前 (lenA - lenB) 步使得 A B 一样长 int count = lenA - lenB;
while(count != 0){ headA = headA.next;
count --; }
}else if(lenA < lenB){ // A 较长 A 首先向前 (lenA - lenB) 步使得 A B 一样长
int count = lenB - lenA; while(count != 0){
headB = headB.next; count --;
} }
while(headA != null && headA.val != headB.val ){
headA = headA.next; headB = headB.next;
}
return headA; }
private int getLen(ListNode head){
int count = 0; while(head != null){
count ++; head = head.next;
} return count;
}
`` }

0 赞同 0 条回复

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

共以下 53 个回答

Definition for singly-linked list.

class ListNode:

def init(self, x):

self.val = x

self.next = None

# 回答此问题取消回复

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

共以下 53 个回答

Definition for singly-linked list.

class ListNode:

def init(self, x):

self.val = x

self.next = None

# 回答此问题 取消回复

# 回答此问题取消回复