【链表专题】剑指 Offer 52. 两个链表的第一个公共节点-跟着帅地玩副业，开拓第二曲线PlayOffer

喵喵神教🐈 普通 2023年10月17日下午2:08

两个链表第一个公共节点，java。思路很重要，因为A+B的长度是固定的，所以循环后有可能达到重合节点，也有可能是null
”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;}

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

hyjob 普通 2023年8月3日下午4:19

【两个链表的第一个公共节点】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) {
        int A = 0;
        int B = 0;
        ListNode* p = headA;
        while (p) {
            A ++;
            p = p->next;
        }
        p = headB;
        while (p) {
            B ++;
            p = p->next;
        }
        int diff = abs(A - B);
        if (A < B) {
            swap(headA, headB);
        }
        while (diff --) {
            headA = headA->next;
        }
        ListNode* index1 = headA;
        ListNode* index2 = headB;
        while (index1 && index2) {
            while (index1 != index2) {
                index1 = index1->next;
                index2 = index2->next;
            }
            return index1;
        }
        return nullptr;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年8月1日下午10:51

打卡

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

0 赞同 0 条回复

Rona 普通 2023年7月17日下午11:37

思路：假定共同尾部分为C，前面分别为A,B。A+C+B = B+C+A, 此时双指针到达同一节点
注意：链表A走到尾换链表B走时，已经节点前进了，因此不能再按.next来，所以这里应该是选择条件
时间复杂度：O(N+M)
空间复杂度：O(1)

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

0 赞同 0 条回复

夏唐普通 2023年7月17日下午3:41

打卡

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

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA and not headB:
            return None
        A, B = headA, headB
        while A!=B:
            A = A.next if A else headB
            B = B.next if B else headA
        return A

0 赞同 0 条回复

李敏普通 2023年7月16日下午1:55

//代码
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 条回复

hi 普通 2023年7月15日下午3:12

指针相等时，走过的路程相等
具体操作过程为，每个指针遍历完第一个链表就开始遍历另一个链表

/**
 * 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* q = headA;
        ListNode* p = headB;

        while(q != p)
        {
            if(q) q = q -> next;
            else q = headB;
            if(p) p = p -> next;
            else p = headA;
        }

        return q;
    }
};

0 赞同 0 条回复

始料未及普通 2023年7月15日下午3:03

双指针可以走的步长不同，也可以相同，找相同节点可以循环。走完A走B，到相同节点的步数是一致的。如果没有公共节点，最后都指向null
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 A=headA;
ListNode B=headB;
while(A!=B){
if(Anull){
A=headB;
}else{
A=A.next;

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

        }
    }
    return A;
}

}

0 赞同 0 条回复

wowo 普通 2023年7月14日上午8:14

如果有公共节点，链表A+链表B非公共部分长度=链表B+链表A非公共部分长度，指针A到末尾时指向链表B的头，指针B到末尾时指向链表A的头，指针A和B会在公共节点处重合。如果没有公共节点，指针A和B会同时指向Null

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if headA is None or headB is None:
            return None
        else:
            pA = headA
            pB = headB

            while (pA != pB):
                if pA.next is None and pB.next is None:
                    return None

                if pA.next is None:
                    pA = headB
                else:
                    pA = pA.next

                if pB.next is None:
                    pB = headA
                else:
                    pB = pB.next

            return pA

0 赞同 0 条回复

洪小哲普通 2023年7月12日下午11:14

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto* A = headA;
        auto* B = headB;
        while(A != B)  //交换起点，如果有交点，则在交点处退出；如果没交点，则同时到达末尾节点之后的nullptr节点，同样退出
        {
            A = A ? A->next : headB;
            B = B ? B->next : headA;
        }
        return A;
    }
};

0 赞同 0 条回复

望仔普通 2023年7月11日下午11:44

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    /*
        就让两个指针分别从a、b出发，走到底了，再交换起点
        这样子，如果存在交点，设a：m+k, b: n+k
        此时指针的路径长度分别为: m+k+n, n+k+m
    */

    pA, pB := headA, headB
    if headA == nil || headB == nil {
        return nil
    }

    for pA != nil || pB != nil {
        if pA == nil {
            pA = headB
        }

        if pB == nil {
            pB = headA
        }

        if pA == pB {
            break
        }

        pA, pB = pA.Next, pB.Next
    }

    return pB
}

0 赞同 0 条回复

Edenms-u 普通 2023年7月11日下午9:31

/**
 * 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 *A = headA, *B = headB;

    while(A != B){
        A = A ? A->next : headB;
        B = B ? B->next : headA;
    }

    return A;
}

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

0 赞同 0 条回复

我家旺仔普通 2023年7月11日下午4:10

打卡
class Solution {
public:
ListNode getIntersectionNode(ListNode *headA, ListNode *headB) {
int al = 0,bl = 0;
ListNode na = headA, *nb = headB;
while(na){
al++;
na = na ->next;
}
while(nb){
bl++;
nb = nb ->next;
}
na = headA;
nb = headB;
if(al > bl){
for(;al>bl;al–){
na = na->next;
}
}else{
for(;bl>al;bl–){
nb = nb->next;
}
}
while(na && nb && na != nb){
na = na->next;
nb = nb->next;
}
if (nb != nullptr){
return nb;
}
else
return nullptr;
}
};

0 赞同 0 条回复

momo 普通 2023年7月11日上午8:56

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

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

mpweixin用户普通 2023年7月10日下午8:03

//打卡
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode *> set;
        while(headA){
            set.insert(headA);
            headA = headA->next;
        }
        while(headB){
            if(set.find(headB) != set.end()){
                return headB;
            }
            headB = headB->next;
        }
        return nullptr;
    }
};

0 赞同 0 条回复

NullPointerException 普通 2023年7月10日下午7:55

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//拉齐长度，再判断
int l1num=0;
int l2num=0;
ListNode l1=headA;
ListNode l2=headB;
while(l1!=null)
{
l1num++;
l1=l1.next;
}
while(l2!=null)
{
l2num++;
l2=l2.next;
}
l1=headA;
l2=headB;
while(l1num>l2num&&l1!=null)
{
l1=l1.next;
l1num–;
}

    while(l2num>l1num&&l2!=null)
    {
        l2=l2.next;
        l2num--;
    }
    while(l1!=null&&l2!=null)
    {
        if(l1==l2)
        {
            return l1;
        }
        l1=l1.next;
        l2=l2.next;
    }
        return null;
}

}

0 赞同 0 条回复

周小二普通 2023年7月10日上午2:36

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //判断初始链表
        if (headA == null || headB == null) return null;
        ListNode p1 = headA, p2 = headB;
        //指针p1或p2相同（或同时为null）时结束循环
        while ( p1 != p2 ) {
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA : p2.next;
        }
        return p1;
    }
}

0 赞同 0 条回复

小北普通 2023年7月9日下午11:49

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

0 赞同 0 条回复

w 普通 2023年7月9日下午10:36

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指向链表B
            A = A == null? headB : A.next; 
            B = B == null? headA : B.next;
        }
        return A;
    }
}

0 赞同 0 条回复

@ 李小二普通 2023年7月9日下午10:01

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

        ListNode A = headA; // 创建指针A，指向链表A的头节点
        ListNode B = headB; // 创建指针B，指向链表B的头节点

        while (A != B) { // 当指针A和指针B不相等时，继续遍历
            // 如果指针A到达链表A的尾部，则将其重定向到链表B的头节点
            A = A == null ? headB : A.next;
            // 如果指针B到达链表B的尾部，则将其重定向到链表A的头节点
            B = B == null ? headA : B.next;
        }

        return A; // 返回相交节点（如果存在），如果不存在相交节点则返回null

    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月9日下午6:55

代码实现：
class ListNode:
def init(self, x=None):
self.data = x
self.next = None

class Solution(ListNode):

def IntersectionNode(self, headA, headB):
    hash_lis = []

    cur = headA

    while cur!= None:
        hash_lis.insert(cur)
        cur = cur.next

    cur = headB

    while cur!=None:
        if cur in hash_lis:
            return cur
        cur = cur.next

    return None

0 赞同 0 条回复

神经蛙普通 2023年7月9日下午5:56

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

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 特殊情况
        if (headA == null || headB == null) {
            return null;
        }

        // 定义变量
        ListNode pA = headA;
        ListNode pB = headB;

        // 当走完两个链表长度时返回null or pa = pb
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }

        return pA;
    }
}

0 赞同 0 条回复

3A87 普通 2023年7月9日下午3:01

/**
 * 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) return nullptr;
        if(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 条回复

刹那芳间普通 2023年7月9日下午2:37

/**
    特殊情况，判断链表是否为空，一方为空直接返回null
    用a、b指针分别遍历两个链表，遇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 条回复

Evilluu 普通 2023年7月9日下午1:42

class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
A,B=0,0
cur1 = headA
cur2 = headB
while cur1:
cur1=cur1.next
A+=1
while cur2:
cur2=cur2.next
B+=1
cur1,cur2=headA,headB
if A>B:
for _ in range(A-B):
cur1=cur1.next
if B>A:
for _ in range(B-A):
cur2=cur2.next
while cur1:
if cur1 cur2:
return cur1
else:
cur1 = cur1.next
cur2 = cur2.next
return None
计算长度，从公共剩余长度开始比较

0 赞同 0 条回复

mpweixin用户普通 2023年7月9日下午1:35

参考的题解，自己没想出来。双指针

/**
 * 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 == NULL || headB == NULL)return NULL;
        ListNode* pa = headA;
        ListNode* pb = headB;

        while(pa!=pb){
            if(pa==nullptr){
                pa=headB;
            }
            else pa=pa->next;
            if(pb==nullptr){
                pb=headA;
            }
            else pb=pb->next;
        }
        return pa;
    }
};

0 赞同 0 条回复

finalrgy 普通 2023年7月9日上午10:13

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    lenA := getLen(headA)
    lenB := getLen(headB)
    lenDiff := lenB - lenA
    // 确保A是短 B是长
    if lenA > lenB {
        temp := headA
        headA = headB
        headB = temp
        lenDiff = lenA - lenB
    }
    for i := 0; i < lenDiff; i += 1 {
        headB = headB.Next
    }
    for headA != nil {
        if headA == headB {
            break
        }
        headA = headA.Next
        headB = headB.Next
    }
    return headA
}

func getLen(head *ListNode) int {
    len := 0
    for head != nil {
        head = head.Next
        len += 1
    }
    return len
}

上面是计算两个链表节点数量差的方法
2.时间复杂度O(N) 空间复杂度O(1)

0 赞同 0 条回复

mpweixin用户普通 2023年7月9日上午9:33

class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headAnull || headB null)return null;
ListNode cur1=headA;
ListNode cur2=headB;
while(cur1!=cur2){
cur1=cur1null?headB:cur1.next;//不是？cur2 ，会出现空指针，两个都指向空后报错程序结束
cur2=cur2null?headA:cur2.next;
}
return cur1;
}
}
时间复杂度O（n）
空间复杂度O（1）

0 赞同 0 条回复

新禾普通 2023年7月9日上午12:42

同时遍历，要么在共同节点，要么同时为空
时间复杂度：O(m+n)
空间复杂度O1
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA null || headB null) return null;
ListNode pa = headA;
ListNode pb = headB;
while (pa != pb) {
pa = pa null ? headB : pa.next;
pb = pb null ? headA : pb.next;
}
return pa;
}
}

0 赞同 0 条回复

ppopp 普通 2023年7月9日上午12:09

/**
两个链表同时遍历完最终停留在共同节点或者同时为空值
* 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;
ListNode *pb = headB;
while(pa != pb){
pa = (pa != nullptr ? pa->next : headB);
pb = (pb != nullptr ? pb->next : headA);
}
return pa;
}
};

0 赞同 0 条回复

人生何处不青山普通 2023年7月8日下午11:39

估计也就我用TS了

/**
 * 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, b = headB;
    while (a !== b) {
        a = a ? a.next : headB;
        b = b ? b.next : headA;
    }
    return a;
};

0 赞同 0 条回复

ㅤ 普通 2023年7月8日下午11:36

/**
     * 剑指 Offer 52. 两个链表的第一个公共点
     * https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
     * 思路: 1⃣ 长链表先走 （长链表长度 - 短链表长度） 步，再一块走找公共节点
     *      2⃣ 两链表一块走，当走到链表尾部时，重新再从起点走，最后两个链表终究会相遇（链表所走长度 = 公共点前的长度 + 整条链表长度）
     */
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 特殊情况
        if(headA == null || headB == null){
            return null;
        }
        // 双链表一块走，直至走到公共点
        ListNode tempA = headA, tempB = headB;
        while(tempA != tempB){
            // 通过三元运算符，计算链表循环起点
            tempA = tempA == null ? headA : tempA.next;
            tempB = tempB == null ? headB : tempB.next;
        }
        return tempA;
    }

0 赞同 0 条回复

富城普通 2023年7月8日下午10: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 条回复

Rico 普通 2023年7月8日下午9:56

if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode *pA = headA, *pB = headB;
       //指针 pA 移到链表headB 的头节点，指针 pB 移到链表 headA 的头节点，然后两个指针继续移动

 while (pA != pB) {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;

0 赞同 0 条回复

Fighting boy😀 普通 2023年7月8日下午9:53

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

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月8日下午9:45

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

CKX 普通 2023年7月8日下午9:23

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    //分别计算A、B的长度
    A_length := 1
    B_length := 1

    tempA := headA
    tempB := headB
    for tempA != nil {
        A_length++
        tempA = tempA.Next
    }
    for tempB != nil {
        B_length++
        tempB = tempB.Next
    }

    //根据长度差设置双指针
    if A_length > B_length {
        for i := 0; i < (A_length - B_length); i++ {
            headA = headA.Next
        }
    } else {
        for i := 0; i < (B_length - A_length); i++ {
            headB = headB.Next
        }
    }

    for headA != nil && headB != nil {
        if headA == headB {
            return headA
        }
        headA = headA.Next
        headB = headB.Next
    }

    return nil

}

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

0 赞同 0 条回复

mpweixin用户普通 2023年7月8日下午9:08

/**
 * 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 curA = headA;
        ListNode curB = headB;

        /*双指针法，同时分别逐结点遍历，当curA到达headA的尾部时，重新定位到headB的头结点，
        curB同理
        即使得两个结点最终都走同样的步数相遇
        */
        // 更容易理解的方法，是使用哈希表，将A中所有的结点存入哈希表，再一一与B中结点比较
        while(curA!=curB){
            curA = curA==null? headB:curA.next;
            curB = curB==null?headA:curB.next;
        }
        return curA;
    }
}

时间复杂度：O（n）
空间复杂度：O（1）

0 赞同 0 条回复

普通 2023年7月8日下午9:04

c++ 代码相爱的人总会相遇
class Solution {
public:
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)
{
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 条回复

#00456B 普通 2023年7月8日下午8:52

写了两个解法，但其实本质是一样的，都是双指针。只是2相当于1的拆解，形象理解了过程。

解法一

用p、q两个节点来分别遍历headA和headB，在遍历的时候判断当前节点是否为空，若为空就取另一个链表的开头。就是相当于把两个链表连接，p在ABABAB···中遍历，q在BABABA···中遍历，变成了一个追及问题，他们总会遇上的。

/**
 * 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* p = headA;
        ListNode* q = headB;
        while(p != q){
            p = (p == NULL) ? headB:p->next;
            q = (q == NULL) ? headA:q->next;
        }
        return p;
    }
};

解法二

先遍历两个链表得到长度，根据两个链表的长度差，让长的链表先走gap步，然后共同遍历，若有共同节点就输出

/**
 /**
 * 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 lenA = 0, lenB = 0;
        ListNode* curA = headA;
        ListNode* curB = headB;
        while(curA != NULL){
            curA = curA->next;
            lenA++;
        }
        while(curB != NULL){
            curB = curB->next;
            lenB++;
        }
        //让lenA永远大于等于lenB
        if(lenAnext;
        }
        while(curA != curB){
            curA = curA->next;
            curB = curB->next;
        }
        return curA;
    }
};

0 赞同 0 条回复

坏掉的世界永久会员 2023年7月8日下午8:28

代码

/**
 * 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 NULL;
        }
        auto p = headA;
        auto q = headB;
        while(p != q){

            p = (p != NULL)?p -> next:headB;
            q = (q != NULL)?q -> next:headA;
        }
        return p;
    }
};

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月8日下午8:10

代码如下

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

offer收割机普通 2023年7月8日下午5:49

public class 两个链表的第一个公共节点 {
    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 条回复

Ad. 普通 2023年7月8日下午5:46

这题没有想出来，看完题解，理解了。我将思路拆解如下：
1. 要判断两个链表有没有相交，翻译成代码就是链表节点是否相等 -> A = B
2. 要做到这一步的关键，就得先让他们能同时走，且最后都能一起走到终点。也就是他们走的长度要一样。
3. 而原始链表长度不一定相同，我们要通过一些方法，让长的那一个链表先走几步，达到和短链表一样的步数。
4. 一种方法比较好想的是，算出两个链表的长度差值x，让长链表走x步。再通过第一点提到的条件，就能找到相交点。
5. 另一种方法，也就是下面这种比较巧一点的方法。就是通过循环走链表的形式，最终达到步数的统一。走到空时，继续从另一条链表开始走，在某一个时刻，两个指针会统一步伐。

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 ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }
}

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

0 赞同 0 条回复

小季同学普通 2023年7月8日下午5:14

双指针

var getIntersectionNode = function(headA, headB) {
    // 双指针,因为相交之后，后面的节点数是一样的，所以两个指针一起走
    // 边界判断
    if(headA === null || headB === null) return null
    let ha = headA
    let hb = headB
    while(ha !== hb) {
        ha = ha === null ? headB : ha.next;
        hb = hb === null ? headA : hb.next;
    }
    return ha
};

0 赞同 0 条回复

mpweixin用户普通 2023年7月8日下午3:34

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, s
        //kipB = 3
        //输出：Reference of the node with value = 8
        Set<ListNode> set = new HashSet<>();
        while (headA!=null) {
            set.add(headA);
            headA = headA.next;
        }
        while (headB!=null) {
            if (set.contains(headB))
                return headB;
            else
                headB = headB.next;
        }
        return null;
    }
}

0 赞同 0 条回复

片言莫语普通 2023年7月8日下午3:20

思路
1. 设置两个指针，记为A和B，一开始A指向链表A的头节点，B指向链表B的头节点。
2. 让A和B同时向后移动，当A到达链表A的尾部时，让A重新定位到链表B的头节点；当B到达链表B的尾部时，让B重新定位到链表A的头节点。
3. 当A和B相遇时，相遇的点即为两个链表的第一个公共节点。如果没有公共节点，那么最后A和B会同时为null。
为什么这个算法可以找到第一个公共节点呢？原因在于，这个算法可以消除两个链表长度的差异。假设链表A的长度为a+c，链表B的长度为b+c，其中c为两个链表的公共部分，a为链表A的独有部分，b为链表B的独有部分。那么，按照算法，A指针实际上走过的路径为a+c+b，B指针走过的路径为b+c+a，两者相同。这意味着，如果有公共节点，A和B一定会在公共节点处相遇；如果没有公共节点，A和B一定会在两个链表末尾处相遇，此时A和B都为null。
代码
时间复杂度：O(m+n) m，n分别是两个链表的长度
空间复杂度：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;   //返回A,B都可以
    }
}

0 赞同 0 条回复

艺普通 2023年7月8日下午1:41

“`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 == 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+m)
//空间复杂度O(1)

0 赞同 0 条回复

H、普通 2023年7月8日下午1:30

双指针，时间 O(M+N)，两个链表的长度；空间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){
            if(A == null){
                A = headB;
            }else {
                A = A.next;
            }

            if(B == null){
                B = headA;
            }else {
                B = B.next;
            }
        }
        return A;

    }
}

0 赞同 0 条回复

KCOcean 普通 2023年7月8日下午1:25

代码

 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *a,*b;
        if (!headA || !headB) return nullptr;
        a = headA;
        b = headB;
        while(a != b){
            a = a ? a->next : headB;
            b = b ? b->next : headA;
        }
        return a;
    }

0 赞同 0 条回复

枫梓。普通 2023年7月8日下午1:12

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;
    }
};

双指针两个链表的第一个公共节点。 O(m+n)

0 赞同 0 条回复

mpweixin用户普通 2023年7月8日下午1: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) {
if(headA null || headB null) return null;
ListNode A = headA;
ListNode B = headB;

    while(A != B ){
        A = (A == null) ? headB : A.next;//若A为空 则继续走B的路
        B = (B == null) ? headA : B.next;//若B为空，则继续走A的路
    }
    return A;//返回A和B都一样 都是公共节点
    }

}

0 赞同 0 条回复

爱吃胡萝卜🥕的兔子🐰 普通 2023年7月8日下午12:46

—

“`/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
a := headA
b := headB
for a != b{
if a == nil{
a = headB
}else {
a = a.Next
}

    if b == nil{
        b = headA
    }else{
        b = b.Next
    }
}

return a

}

“`
打卡

0 赞同 0 条回复

Mooby 普通 2023年7月8日上午11: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 (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月8日上午10:36

/**
 * 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;
        ListNode *q = headB;
        while (p != q){
            p = p == nullptr ? headB : p->next;
            q = q == nullptr ? headA : q->next;
        } 

        return q;
    }
};

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

0 赞同 0 条回复

波雅汉库克普通 2023年7月8日上午4:00

/**
 * 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* listA = headA;
        ListNode* listB = headB;
        while(listA!=listB){
            listA = listA -> next;
            listB = listB -> next;
            if(listB!=nullptr && listA == nullptr){
                listA = headB;
            }
            if(listA!=nullptr && listB == nullptr){
                listB = headA;
            }
        }
        return listA;
    }
};

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

0 赞同 0 条回复

Luminous 普通 2023年7月8日上午12:24

/**
 * 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(m+n)
空间复杂度：O(1)

0 赞同 0 条回复

是非之欢普通 2023年7月8日上午12:23

代码

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *h1 = headA;
        ListNode *h2 = headB;
        while(h1 != h2){
            if(h1){
                h1 = h1->next;
            }
            else{
                h1 = headB;
            }
            if(h2){
                h2 = h2->next;
            }
            else{
                h2 = headA;
            }
        }
        return h1;
    }
};

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月8日上午12:19

Day1：下面是代码

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

mpweixin用户普通 2023年7月8日上午12:13

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

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        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月7日下午11:27

”C++
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headANULL&&headBNULL)return NULL;

    ListNode* newheada=headA;
    ListNode* newheadb=headB;
   while(newheada!=newheadb)

    {
        newheada=newheada!=NULL?newheada->next:headB;
        newheadb=newheadb!=NULL?newheadb->next:headA;
    }
    return newheada;

}

};
执行用时：40 ms

0 赞同 0 条回复

阿尚普通 2023年7月7日下午11:23

//遍历长度
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA null || headB null) return null;

    ListNode la = headA;
    ListNode lb = headB;
    int k = 0;

    while(la != null){
        k++;
        la = la.next;
    }
    while(lb != null){
        k--;
        lb = lb.next;
    }

    if(k < 0){
        k = -k;
        ListNode temp = headA;
        headA = headB;
        headB = temp;
    }

    la = headA;
    lb = headB;

    while(k > 0){
        la = la.next;
        k--;
    }

    while(la != null){
        if(la == lb) return la;
        la = la.next;
        lb = lb.next;
    }

    return null;
}

}

0 赞同 0 条回复

June 普通 2023年7月7日下午10:57

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

时间复杂度 O(N) 空间复杂度 O(1)

0 赞同 0 条回复

Terence💧 普通 2023年7月7日下午10:55

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    l1, l2 := headA, headB
    if l1 == nil || l2 == nil {return nil}

    for l1 != l2 {
        if l1 == nil {
            l1 = headB
        }else {
            l1 = l1.Next
        }
        if l2 == nil {
            l2 = headA
        }else{
            l2 = l2.Next
        }
    }

    return l1
}

时间复杂度：O(M+N)

0 赞同 0 条回复

桎梏普通 2023年7月7日下午9:50

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(1)
时间复杂度:O(m+n)

0 赞同 0 条回复

ONE PIECE 普通 2023年7月7日下午9:41

/**
 * 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 l=headA;
        ListNode r=headB;
        int k=2;
        while(l!=r){
            if(l==null){
                l=headB;
            }else{
                l=l.next;
            }
            if(r==null){
                r=headA;
            }else{
                r=r.next;
            }
        }
        return l==null?null:l;
    }
}

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

0 赞同 0 条回复

北辰普通 2023年7月7日下午9:15

```java
static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set set = new HashSet<>();
        while(headA!=null) {
            set.add(headA);
            headA =headA.next;
        }
        while(headB!=null) {
            if(set.contains(headB)){
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
```

时间复杂度：O（m+n)
空间复杂度：O（max(m,n))

0 赞同 0 条回复

云雀普通 2023年7月7日下午9:00

它说必须包含中文

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        pre = head
        cur = pre
        for i in range(k):
            cur = cur.next
        while cur:
            pre = pre.next
            cur = cur.next
        return pre

0 赞同 0 条回复

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

共以下 68 个回答

解法一

解法二

# 回答此问题取消回复

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

共以下 68 个回答

解法一

解法二

# 回答此问题 取消回复

# 回答此问题取消回复