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

mpweixin用户普通 2024年5月14日上午11:55

d打卡成功！

0 赞同 0 条回复

刘成志永久会员 2023年10月9日上午11: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) {
ListNode *NodeA = headA;
ListNode *NodeB = headB;
//遍历两个链表，直到链表指向末尾后将链表指向另一个链表的头，继续遍历直到两个节点相等
while(NodeA != NodeB)
{
if(NodeA != nullptr)
{
NodeA = NodeA->next;
}
else
{
NodeA = headB;
}
if(NodeB != nullptr)
{
NodeB = NodeB->next;
}
else
{
NodeB = headA;
}
}
return NodeA;
}
};
时间复杂度为O(m+n)，空间复杂度为O(1)。

0 赞同 0 条回复

慎言永久会员 2023年8月31日下午10:35

###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(headANULL || headBNULL) return NULL;
ListNode tmpA=headA,*tmpB=headB;
while(tmpA!=tmpB){
tmpA=tmpANULL?headB:tmpA->next;
tmpB=tmpBNULL?headA:tmpB->next;
}
return tmpA;
}
};

0 赞同 0 条回复

mpweixin用户普通 2023年8月23日上午11:44

1.构建A，B
2.A= A.next if A else headB
B= B.next if B else headA
3.return = A

0 赞同 0 条回复

黎明之前普通 2023年8月23日上午11:03

//设置两个链表同时分别移动的两个链表，如果个链表中有公共的节点则可以返回节点如果没有则返回空
if(headANULL||headB NULL)
{
return NULL;
}
ListNode *A= headA;
ListNode *B = headB;
while(A!=B)
{
A= A?A->next:headB;
B= B?B->next:headA;
}
return A;

0 赞同 0 条回复

我一定要坚持打卡普通 2023年8月23日上午8:59

自己写的测试用例和题解
使用的是双指针长链表长度-短链表长度并移动长链表指针使两者指针共同移动到公共节点即可

 package day1;

public class 剑指Offer52两个链表的第一个公共节点 {
    
    static ListNode  getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null||headB == null ) {
            return null;    
        }
        ListNode temp1 = headA;
        ListNode temp2 = headB;
        int i = 0;
        int j = 0;
        while (temp1 != null) {
            i++;
            temp1=temp1.next;
        }

        while (temp2 != null) {
            j++;
            temp2=temp2.next;
        }

        if (i>=j) {
            temp1=headA;
            temp2=headB;
            i=i-j;// 设定为两个链表的差，并且先移动headA链表i-j个长度               
            for (int i2 = 0; i2 < i; i2++) {
                if (temp1!=null) {
                    temp1=temp1.next;
                    }
            }   
        }else {
            temp1=headA;
            temp2=headB;
            j=j-i;// 设定为两个链表的差，并且先移动headA链表i-j个长度               
            for (int j2 = 0; j2 < j; j2++) {
                if (temp2!=null) {
                    temp2=temp2.next;
                    }
            }
            
        }
        while (temp1!=temp2&&temp1!=null&&temp2!=null) {
            temp1=temp1.next;
            temp2=temp2.next;
        }
        if (temp1==temp2) {
            return temp1;
        }
        return null;
    }
    
    public static void main(String[] args) {
//      这里测试用例 先对list列表赋值一个,再用循环进行插入,不然下边不方便操作
        ListNode list1  =new ListNode(1);
        ListNode list2  =new ListNode(2);
        ListNode temp1= list1;
        ListNode temp2= list2;
        
        /**
         * 公共链表
         */
        ListNode list  =new ListNode(100);
        ListNode temp= list;
        for (int i = 1; i <= 5; i=i+1) {
            temp.next=new ListNode(i);
            temp=temp.next;
        }//0 1 2 3 4 5

        
        
        /**
         * 下边俩是单独列表
         */
        for (int i = 3; i <= 15; i=i+2) {
            temp1.next=new ListNode(i);
            temp1=temp1.next;
        }// 1 3 5 7 9
        temp1.next = list;
        for (int i = 4; i <= 10; i=i+2) {
            temp2.next=new ListNode(i);
            temp2=temp2.next;
        }// 2 4 6 8 10

        temp2.next = list;
        temp= list;

        while (temp!=null) {
        System.out.println(temp);
        temp=temp.next;
    }
        System.out.println("*************");    
        
        temp1=list1;
        while (temp1!=null) {
        System.out.println(temp1);
        temp1=temp1.next;
    }
        
        System.out.println("*************");
        temp2=list2;
        while (temp2!=null) {
            System.out.println(temp2);
            temp2=temp2.next;
        }
        System.out.println("*************");
        /**
         * 这里修改
         */
        temp1=getIntersectionNode(list1,list2);
        System.out.println(temp1);
    }
    
    
    
    

}

0 赞同 0 条回复

Serena 普通 2023年8月19日下午3:59

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // //第一种：计算a.b的长度，根据差值将长链表的指针提前K个位置，再一起遍历a.b
        // int lengthA=0;
        // int lengthB=0;
        ListNode A=headA;
        ListNode B=headB;
        // while(A!=null){
        //     lengthA++;
        //     A=A.next;
        // }
        // while(B!=null){
        //     lengthB++;
        //     B=B.next;
        // }
        // //将指针对齐
        // A=headA;
        // B=headB;
        // if(lengthA>lengthB){
        //     for(int i=0;i<lengthA-lengthB;i++){
        //         A=A.next;
        //     }
        // }else{
        //     for(int i=0;i<lengthB-lengthA;i++){
        //         B=B.next;
        //     }
        // }
        // //找交点，不相交为Null
        // while(A!=B){
        //     A=A.next;
        //     B=B.next;
        // }
        // return A;

        //第二种方法：两个链表都从头结点开始，空了就从对方链表继续遍历（相当于饶了一圈，最后还是会相交）
        while(A!=B){
            A= A==null ? headB:A.next;
            B= B==null ? headA:B.next; 
        }
        return A;
    }
}

0 赞同 0 条回复

Di questa storia sempre a lie to 普通 2023年8月19日下午3:33

/**
* 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;
while(pA!=pB)
{
pA=pAnullptr? headB : pA->next;
pB=pBnullptr? headA: pB->next;
}
return pA;
}
};
时间复杂度：O(m+n)
空间复杂度： O(1)

0 赞同 0 条回复

梧葳普通 2023年8月18日上午1:17

先来个简单的暴力解法（总长 – 指定长度 = 返回位置），据说还有双指针形式（如总长5，指定2，fast跑2剩3，slow跟它同时跑3剩2，slow剩下的刚好为返回长度）

struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    // 判空
    if (head == NULL || k < 0) {
        return NULL;
    }
    // 算出总长len
    int len_total = 1;
    int len_target = 0;
    struct ListNode* tmp = head;
    while (tmp != NULL) {
        tmp = tmp->next;
        len_total++;
    }
    // 算出指定长度
    len_target = len_total - k;
    tmp = head;
    for (int i = 1; i < len_target; i++) {
        tmp = tmp->next;
    }
    return tmp;
}

1 赞同 0 条回复

谁仁普通 2023年8月17日上午1:44

struct node * getInterOneNode(struct node *heada,struct node *headb)
{
int lena=0,lenb=0,tag=0;
struct node * p = heada;
struct node * q = headb;

//获取长度，两个链表的
while(p != NULL)
{
    lena++;
    p = p->next;
}
    while(q != NULL)
{
    lenb++;
    q = q->next;
}
p = heada;
q = headb;

//链表对齐动作，对齐到相同起始位
tag = abs(lena - lenb);
if(lena > lenb)
{
    for(int i = 0 ;i< tag;i++)
    {
        p=p->next;
    }
}
else
{
    for(int i = 0 ;i< tag;i++)
    {
        q=q->next;
    }
}
//开始寻找第一个相交节点
while(P !=NULL && q != NULL)
{
    if(p == q)
    {
        return p;
    }
    p=p->next;
    q=q->next;
}
return NULL;

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

0 赞同 0 条回复

海浪漂哇漂普通 2023年8月16日下午8:29

交替遍历
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A = headA;
ListNode B = headB;
while(headA != headB){
headA = headA != null ? headA.next : B;
headB = headB != null ? headB.next : A;
}
return headA;
}
}

0 赞同 0 条回复

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

//先将公共节点的意思理解了
//后面才好写解题
//时间复杂度为O(m+n);
//空间复杂度为O(1);
class Solution {
public:
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 条回复

sc_Yang 普通 2023年8月16日上午11:49

哈希存储法：空间复杂度：o(m)，时间复杂度：o(m)
双指针法：空间复杂度：o(1)，时间复杂度：o(m+n)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    // 哈希列表法
    ListNode *unorder_getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA==NULL||headB==NULL){
            return NULL;
        }
        unordered_set visited;
        ListNode* ptrA = headA;
        while(ptrA){
            visited.insert(ptrA);
            ptrA = ptrA->next;
        }
        ListNode* ptrB = headB;
        while(ptrB){
            // 如果原无序列表存在PTRB，则表示是公共节点
            if(visited.count(ptrB)){
                return ptrB;
            }
            ptrB = ptrB->next;
        }
        // 一直没返回则表示无交集
        return NULL;
    }
    // 双指针法
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA==NULL||headB==NULL){
            return NULL;
        }
        ListNode* ptrA = headA;
        ListNode* ptrB = headB;
        while(ptrA!=ptrB){
            ptrA = (ptrA==NULL? headB : ptrA->next);
            ptrB = (ptrB==NULL? headA : ptrB->next);
        }
        return ptrA;
    }
};

0 赞同 0 条回复

Miracle· 普通 2023年8月15日下午10:43

时间复杂度：o(n+m)，空间复杂度：o(1)
思路；两个指针同时走，当一个指针为空时，从另一个链表的头指针开始出发，走到最后两个指针如果相等则返回，返回nullptr代表没有相交节点，否则返回节点即为相交节点。
/**
* 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) {
if (pa != nullptr) pa = pa->next;
else pa = headB;
if (pb != nullptr) pb = pb->next;
else pb = headA;
}
return pa;
}
};

0 赞同 0 条回复

Delete隐身普通 2023年8月15日下午10:08

思路：两个指针同时走，当一个指针为空时，则从另一个链表头节点开始出发；然后另一个指针也为空时，也是开始从另一个链表的头节点开始出发
时间复杂度：O(n + m)，空间复杂度：O(1)
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
while(curA != curB) {
if(curA != null) {
curA = curA.next;
} else {
curA = headB;
}
if(curB != null)
curB = curB.next;
else
curB = headA;
}
return curA;
}
}

0 赞同 0 条回复

💮黧大王.exe 普通 2023年8月15日下午9:36

时间复杂度O(m+n)
空间复杂度O(1)
/**
* 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, *b=headB;
while(a!=b){
a=aNULL?headB:a->next;
b=bNULL?headA:b->next;
}
return a;
}
};

0 赞同 0 条回复

Sheng 永久会员 2023年8月15日下午6:31

时间复杂度O(m+n)空间复杂度O(1)
没有思路，只有暴力遍历的想法。后来直接看的答案的双指针拼接的方法，写出的代码
”’java
//单链表找到两个链表的第一个公共节点
//l1={2,1,4,3};l2={5,6,7,9,4,3}
//思路：两个链表一个前一个后，组成两个新的链表
//l3={2,1,4,3,5,6,7,9,4,3};
//l4={5,6,7,9,4,3,2,1,4,3}
//l3和l4的最后，可以看见拼接后最后几位相等就是公共节点
//时间复杂度O(n)
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB)
{
if(headA null || headB null) return null;
ListNode p1 = headA;
ListNode p2 = headB;
while(p1 != p2) {
// p1 = (p1null ? headB : p1.next);
if(p1 != null) {
p1=p1.next;
}
else {
p1=headB;//开始拼接
}
// p2 = (p2null ? headA : p2.next);
if(p2 != null) {
p2=p2.next;
}
else {
p2=headA;//开始拼接
}
}
return p1;
}
}

0 赞同 0 条回复

QQiing 普通 2023年8月15日下午4:11

 
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){
            if(A == NULL){
                A = headB;
            }else{
                A = A->next;
            }
            if(B == NULL){
                B = headA;
            }else{
                 B = B->next;
            }

        }

    return A;
}

};


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

0 赞同 0 条回复

一个人的风海吹了两遍普通 2023年8月15日上午10:00

先遍历两个链的长度
再使之开始节点都处于同一相对位置
之后逐个比较
注意不是值相等而是节点相等
时间复杂度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(headB==null||headA==null) return null;
        int numA=0, numB=0;
        ListNode A = headA;
        ListNode B = headB;

        while (A!=null){
            A = A.next;
            numA++;
        }
        while (B!=null){
            B = B.next;
            numB++;
        }

        A = headA;
        B = headB;
        if(numA>numB){
            int temp=numA-numB;
            while (temp>0){
                temp--;
                A = A.next;
            }
        } else if (numA<numB) {
            int temp=numB-numA;
            while (temp>0){
                temp--;
                B = B.next;
            } 
        }
        while (A!=B){
            A = A.next;
            B = B.next;
        }
        return A;
    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年8月14日下午10:51

 // 时间O(n+m),空间O(1)
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA||!headB) return NULL;
        ListNode* A = headA,*B = headB;
        while(A != B)
        {
            A = A?A->next:headB;
            B = B?B->next:headA;
        }
        return A;
    }
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月14日下午10:20

ListNode getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA = 0;
int lenB = 0;
if(headA nullptr || headB nullptr){
return nullptr;
}
if(headA headB){
return headA;
}
ListNode p = headA;
while(p){
lenA++;
p=p->next;
}
p = headB;
while(p){
lenB++;
p=p->next;
}
ListNode* pa = headA;
ListNode* pb = headB;
int k = 0;
// listA 长
if(lenA > lenB){
k = lenA – lenB;
while(k){
pa = pa->next;
k–;
}
while(pa && pb && pa != pb){
pa = pa->next;
pb = pb->next;
}
if(pa nullptr){
return nullptr;
}
else{
return pa;
}
}
else{
k = lenB – lenA;
while(k){
pb = pb->next;
k–;
}
while(pa && pb && pa != pb){
pa = pa->next;
pb = pb->next;
}
if(pa nullptr){
return nullptr;
}
else{
return pa;
}
}
}

0 赞同 0 条回复

hhhhh 普通 2023年8月14日下午5:12

过

“`cpp
/**
* 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* l1 = headA;
ListNode* l2 = headB;
int len1 = 1;
while(l1->next != nullptr){
len1++;
l1 = l1->next;
}
int len2 = 1;
while(l2->next != nullptr){
len2++;
l2 = l2->next;
}
if(l1 != l2){
return nullptr;
}
int len = len1 – len2;
if(len > 0){
while(len–){
headA = headA->next;
}
}else{
while(len++ != 0){
headB = headB->next;
}
}
while(headA != headB){
headA = headA->next;
headB = headB->next;
}
return headA;
}
};

0 赞同 0 条回复

逸兴遄飞普通 2023年8月14日上午11:15

时间复杂度：O(n+m)，n 和 m 表示两个链表长度。
空间复杂度：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) {
        // AB任意一方为空，则返回null
        if(headA == null || headB == null){
            return null;
        }
        ListNode A = headA, B = headB;
        // 使用while对两链表的依次值进行对比
        while(A != B){
            // 检查是否遍历到尽头，是则指向B，否则到next
            A = A == null ? headB : A.next;
            B = B == null ? headA : B.next; 
        }
        // 存在AB相等则跳出并返回，返回A或B均可
        return A;
    }
}

0 赞同 0 条回复

晓宇普通 2023年8月14日上午7:58

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        tmpA = headA
        tmpB = headB
        num = 0
        while(headA and headB):
            headA = headA.next
            headB = headB.next
        while(headA):
            tmpA = tmpA.next
            headA = headA.next
        while(headB):
            tmpB = tmpB.next
            headB = headB.next
        while(tmpA and tmpB):
            if tmpA == tmpB:
                return tmpA
            tmpA = tmpA.next
            tmpB = tmpB.next
        return None

本题是主要是双指针遍历过程中，如何使用差值，
比较巧妙的是先获取差值，
然后根据差值让双链表处于同一个起点，
并判断何时相交

0 赞同 0 条回复

漂洋过海去见你永久会员 2023年8月13日下午7:57

#python解题
class Solution(object):
def getIntersectionNode(self, headA, headB):
“””
:type head1, head1: ListNode
:rtype: ListNode
“””
if headA is None or headB is None:
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 条回复

sincere 普通 2023年8月13日下午5:37

思路：双指针 l1、l2 遍历，自己走完了就走另外一个链表，如果存在相交，可以将两个链表分别拼接对方（逻辑上），直到它们相交的第一个节点
复杂度：时间复杂度O(m+n)，空间复杂度O(1)

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        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 条回复

辰北、普通 2023年8月13日下午4:02

//c 找公共点，1看是否为空，两值是否相等，不等的话，不为空各自下移，如果为空就等于另一个链表，然后满足相等跳出循环；

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

    if(inter==NULL){
        inter=headA;
    }else{
        inter= inter->next;
    }
}

return amd;
}

0 赞同 0 条回复

天亮说晚安普通 2023年8月13日下午1:32

思路：循环遍历两列表找到公共值
时间复杂度O(n^2)，空间复杂度O(1)

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        while(p1!=null){
            ListNode p2 = headB;
            while(p2!=null){
                if(p1==p2){
                    return p1;
                }
                p2 = p2.next;
            }
            p1 = p1.next;
        }
        return null;
    }
}

0 赞同 0 条回复

WA 普通 2023年8月13日上午11:05

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

0 赞同 0 条回复

天亮之前普通 2023年8月13日上午10:30

/**
*打卡
* 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 条回复

Jou Siankwa 普通 2023年8月13日上午10:13


class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        ListNode nodeA = headA, nodeB = headB;
        int countA = 0, countB = 0;
        while (nodeA.next != null){
            nodeA = nodeA.next;
            countA++;
        }
        while (nodeB.next != null){
            nodeB = nodeB.next;
            countB++;
        }
        if(nodeA != nodeB){
            return null;
        }
        nodeA = headA;
        nodeB = headB;
        if(countA > countB){
            int temp = countA - countB;
            while (temp-- > 0){
                nodeA = nodeA.next;
            }
        }else if(countB > countA){
            int temp = countB - countA;
            while (temp-- > 0){
                nodeB = nodeB.next;
            }
        }
        while (nodeA != nodeB){
            nodeA = nodeA.next;
            nodeB = nodeB.next;
        }
        return nodeA;
    }

    public static void main(String[] args) {
        ListNode a1 = new ListNode(4);
        ListNode a2 = new ListNode(1);

        ListNode b1 = new ListNode(5);
        ListNode b2 = new ListNode(0);
        ListNode b3 = new ListNode(1);

        ListNode c1 = new ListNode(8);
        ListNode c2 = new ListNode(4);
        ListNode c3 = new ListNode(5);

        a1.next = a2;
        a2.next = c1;
        c1.next = c2;
        c2.next = c3;
        b1.next = b2;
        b2.next = b3;
        b3.next = c1;

        Solution sol = new Solution();
        ListNode listNode = sol.getIntersectionNode(a1, b1);

        System.out.println(listNode.val);

    }
}

先判断是否末尾节点为公共的，是的话下一步判断，否则返回null。
计算长链表比短链表多的个数n，让长链表先走n步，然后长短链表一起往后走，碰到相同的节点时返回。

0 赞同 0 条回复

mpweixin用户普通 2023年8月13日上午3:50

時間複雜度 O(M+N) 空間複雜度 O(1)
具體思路:
因為可能兩條長度不一樣, 我們可以利用一個技巧, 同時從第一條跟第二條起點開始遍歷,
如果到盡頭了則回到另一條的起點, 再繼續往前遍歷, 如果有交點的話, 則兩個遍歷元素會剛好相遇
沒有交點則兩個遍歷元素會在尾端NULL相遇


class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
         ListNode* fast = headA;
         ListNode* slow = headB;


         while (fast != slow) {
            fast = fast ? fast->next : headB;
            slow = slow ? slow->next : headA;

         }
         return slow;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年8月13日上午2:32

时间复杂度：O(M+N), 空间复杂度：O(1)
妙啊，个人理解是把两个链表连接成8的形状，上下两个圈代表两个链表，中间的交点是两个链表重合部分
以例1为例

 
              a2 <-----------a1
              ->             ->
                 c1 ->c2-> c3
              ->             ->
            b3                b1
               <-           <-  
                      b2

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

1 赞同 0 条回复

Marc 普通 2023年8月13日上午1:52

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None  
        l1, l2 = headA, headB
        while l1 != l2:
            if not l1.next and not l2.next:
                return None 
            l1 = l1.next if l1.next else headB
            l2 = l2.next if l2.next else headA 
        return l1

时间O m+n
空间O 1

0 赞同 0 条回复

clown 普通 2023年8月13日上午12:47

程序员的浪漫？走完自己路走你来时的路
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;
}

}

0 赞同 0 条回复

Prime 普通 2023年8月13日上午12:05

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

# 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
        """
        pA, pB = headA, headB
        lenA, lenB = 0, 0
        while pA:
            lenA += 1 
            pA = pA.next 
        while pB:
            lenB += 1
            pB = pB.next

        pA, pB = headA, headB
        if lenA > lenB:
            for i in range(lenA - lenB):
                pA = pA.next
        else:
            for i in range(lenB - lenA):
                pB = pB.next

        while pA != pB:
            pA = pA.next
            pB = pB.next
        return pA

0 赞同 0 条回复

木子有点甜🍒 普通 2023年8月12日下午11:33

“`python
这辈子想不到还能这样
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if not headA or not headB:
return None

    pa = headA
    pb = headB

    while pa != pb:
        if not pa.next and not pb.next:
            return
        if pa.next:
            pa = pa.next
        else:
            pa = headB
        if pb.next:
            pb = pb.next
        else:
            pb=headA
    return pa

0 赞同 0 条回复

. 永久会员 2023年8月12日下午11:22

打卡

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

JustRtn 普通 2023年8月12日下午11:19

两个指针分别遍历两个链表，当走到链表尾后从另一个链表头开始走，最终两个指针会在第一个公共点相遇或者在链表尾后面（null)相遇
时间复杂度O(m+n),空间复杂度O(10);

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

0 赞同 0 条回复

mpweixin用户普通 2023年8月12日下午11:05

打卡

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

mpweixin用户永久会员 2023年8月12日下午10:35

双指针思路，核心点在于让俩指针对齐，不过我写的比较啰嗦。。
时间复杂度：O（m+n）空间复杂度O（1）

lass Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode p = headA, q = headB;
        while( p.next != null && q.next != null) {
            p = p.next;
            q = q.next;
        }
        ListNode startNode1 = null, startNode2 = null;
        if( p.next == null ){
            startNode1 = headB;
            startNode2 = headA;
            while ( q.next != null) {
                startNode1 = startNode1.next;
                q = q.next;
            }

        } else {
            startNode1 = headA;
            startNode2 = headB;
            while (p.next != null) {
                startNode1 = startNode1.next;
                p = p.next;
            }
        }
        while (startNode1 != null) {
            if (startNode1 == startNode2) {
                break;
            }
            startNode1 = startNode1.next;
            startNode2 = startNode2.next;
            }
        return startNode1;

    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年8月12日下午10:22

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

/**
 * 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* h = NULL;
        ListNode* h1 = headA;
        ListNode* h2 = headB;

        if(headA == NULL || headB == NULL) return h;

        while(h1 != h2)
        {
            h1 = h1!=NULL? h1->next:headB;
            h2 = h2!=NULL? h2->next:headA;
        }

        return h1;

    }
};

0 赞同 0 条回复

别扒拉我普通 2023年8月12日下午10:20

1、双指针迭代或HashSet
2、时间复杂度O(n+m),空间复杂度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 p = headA;
        ListNode q = headB;
        while(p != q){
            p = p != null ? p.next : headB;
            q = q != null ? q.next : headA;
        }
        return p;
    }

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

0 赞同 0 条回复

Joel 普通 2023年8月12日下午10:16

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

# 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

        if headA == headB or headB.next == headA:
            return headA
        if headA.next == headB:
            return headB

        dummyA = headA
        dummyB = headB

        # get the length of list1 and list2
        len1 = 1
        len2 = 1
        while True:
            if headA.next != None:
                len1 += 1
                headA = headA.next
            else:
                break
        while True:
            if headB.next != None:
                len2 += 1
                headB = headB.next
            else:
                break
        print(len1, len2)
        if len1 > len2:
            longer, shorter = dummyA, dummyB
        else:
            longer, shorter = dummyB, dummyA
        if len2 > len1:
            for i in range(len2-len1):
                longer = longer.next
        else:
            for i in range(len1-len2):
                longer = longer.next
        while True:
            if longer == None:
                return None
            else:
                if longer == shorter:
                    return longer
                else:
                    longer = longer.next
                    shorter = shorter.next

0 赞同 0 条回复

Scanner 永久会员 2023年8月12日下午10:14

/**
* 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; //有一个为空完全不成立

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

    return A;
}

};

0 赞同 0 条回复

小肸永久会员 2023年8月12日下午9:37

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode initialA = headA, initialB = headB;
        //假设A链表短，B链表长。可以认为A走了一次短的路程后就一直走长的路程。而B走了一次长的路程后就一直走短的路程。而A和B速度一样，所以最后B一定会追上A。
        while (headA != headB) {
            headA = (headA == null ? initialB : headA.next);
            headB = (headB == null ? initialA : headB.next);
        }
        return headA;
    }
}

0 赞同 0 条回复

c 普通 2023年8月12日下午9:32

时间O(n+m) 空间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) {
        ListNode nodeA=headA;
        ListNode nodeB=headB;
        int sizeA=0;
        int sizeB=0;
        while (nodeA!=null){
            sizeA++;
            nodeA=nodeA.next;
        }
        while (nodeB!=null){
            sizeB++;
            nodeB=nodeB.next;
        }
        nodeA=headA;
        nodeB=headB;
        if (sizeA>sizeB){
            for (int i = 0; i < sizeA - sizeB; i++) {
                nodeA=nodeA.next;
            }
        }else {
            for (int i = 0; i < sizeB - sizeA; i++) {
                nodeB=nodeB.next;
            }
        }
        while(nodeA!=null && nodeB!=null){
            if (nodeA==nodeB){
                return nodeA;
            }
            nodeA=nodeA.next;
            nodeB=nodeB.next;

        }
        return null;
    }
}

0 赞同 0 条回复

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

共以下 47 个回答

# 回答此问题取消回复

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

共以下 47 个回答

# 回答此问题 取消回复

# 回答此问题取消回复