晚睡晚起起不来永久会员 2024年3月28日下午11:09

两个指针往前遍历
A走到null 指向B，继续走B的路
B走到null 指向A，继续走A的路
两个指针会相交，这就是他们的公共节点

java
//java代码
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//初始化赋值A B
       ListNode A = headA;
       ListNode B = headB;
//如果为空则退出
       if(A ==null && B == null){
        return null;
       }
//当A和B不等的时候继续往前走
       while(A != B){
//判断A是否走到末尾，走到末尾就走B的路，没有就继续走A的路
        A = A == null ? headB :A.next;
        B = B == null ? headA :B.next;   
       }
//返回A，就是两个相交的地方
       return A;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年3月28日下午10:42

”’python
def getIntersectionNode(self, headA, headB):
“””
:type head1, head1: ListNode
:rtype: ListNode
“””
if not headA or not headB:
return None

    pa = headA
    pb = headB

    while pa != pb:
        pa = headB if pa is None else pa.next
        pb = headA if pb is None else pb.next

        # 如果两个链表没有交点，最终会同时到达尾部，此时 pa 和 pb 都为 None，返回 None
        if pa == None and pb == None:
            return None

    return pa  # 返回交点或者 None

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

0 赞同 0 条回复

熊猫不是猫普通 2024年3月26日下午1:21

“`c++
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *curA = headA;
ListNode *curB = headB;
int lensA = 0, lensB = 0;
while(curA != nullptr) {
lensA++;
curA = curA->next;
}

    while(curB != nullptr) {
        lensB++;
        curB = curB->next;
    }

    curA = headA;
    curB = headB;
    //令curA成为最长链表的头，lensA为其长度
    if (lensB > lensA) {
        swap(lensA, lensB);
        swap(curA, curB);
    }

    //求长度差并末尾对齐
    int gap = lensA - lensB;
    while(gap--) {
        curA = curA->next;
    }
    //遍历
    while(curA != nullptr) {
        if(curA == curB) {
            return curA;
        }
        curA = curA->next;
        curB = curB->next;
    }
    return NULL;
}

};

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

0 赞同 0 条回复

钱大牙普通 2024年3月25日下午11:20

时间复杂度：O(n+m)，n 和 m 表示两个链表长度
空间复杂度：O(1)
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if headA is None and headB is None:
return None
pa = headA
pb = headB
while pa != pb:
if pa:
pa = pa.next
else:
pa = headB
if pb:
pb = pb.next
else:
pb = headA
return pa

0 赞同 0 条回复

June 普通 2024年3月15日下午4:36

// 使用交替遍历
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA null && headB null) {
return headA;
}

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

山月普通 2024年3月13日下午10:03

//求两个链表的第一个交点，思路：双指针，长链表指针先移动使其剩余元素个数与短链表长度一致。然后双指针一起移动，找地址相同处
class Solution {
public:
ListNode getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode curA = headA;
ListNode* curB = headB;
int lenA = 0;
int lenB = 0;
while(curA != NULL)
{
lenA++;
curA = curA->next;
}
while(curB != NULL)
{
lenB++;
curB = curB->next;
}
curA = headA;
curB = headB;
if(lenB > lenA)
{
swap(lenA,lenB);
swap(curA,curB);
}
int gap = lenA-lenB;
while(gap–)
{
curA = curA->next;
}
while(curA != NULL){
if(curA curB)
{return curA;}
curA = curA->next;
curB = curB->next;

    }
    return NULL;

}

};

0 赞同 0 条回复

RunAsOne 普通 2024年3月11日下午4:19

第四次打卡

# 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
        """
        a = headA
        b = headB
        while a!=b:
            if a:
                a = a.next
            else:
                a = headB
            if b:
                b = b.next
            else:
                b = headA
        return b

0 赞同 0 条回复

雨落星空普通 2024年3月10日上午9:14

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

0 赞同 0 条回复

🌈 普通 2024年3月5日下午10:31

/**
* 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 l1 = headA;
ListNode l2 = headB;

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

    return l1;
}

};

当不存在交点时，NULL就被视为交点，因此判断条件不能为l1.next.

0 赞同 0 条回复

e=mc² 普通 2024年3月5日下午9:53

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode tempA = headA;
        ListNode tempB = headB;
        while (tempA != tempB) {
            // 双指针 相当于遍历了A+B/B+A的长度 如果有公共子节点 一定可以同步
            tempA = tempA == null ? headB : tempA.next;
            tempB = tempB == null ? headA : tempB.next;
        }
        return tempA;
    }
}

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

0 赞同 0 条回复

LAVI 普通 2024年3月5日下午2:58

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) m和n为两个链表的长度

0 赞同 0 条回复

YOLO 普通 2024年3月5日上午11:41

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A = headA;
        ListNode *B = headB;
        int lenA=0,lenB=0;
        while(A != NULL){//A,B长度
            lenA++; 
            A = A->next;
        }
        while(B != NULL){
            lenB++; 
            B = B->next;
        }
        A = headA;B = headB;
        if(headA <span class="text-highlighted-inline" style="background-color: #fffd38;"> NULL && headB </span> NULL)
            return NULL;
            if(lenA > lenB){
                for(int i = 0; i<lenA-lenB;i++){
                    A = A->next;
                }
            }
            else{
                for(int i=0;i<lenB-lenA;i++){
                    B=B->next;
                }<br />
            }
            while(A!=B){
                A = A->next;
                B = B->next;
            } 
        return A; 
    }

};

1 赞同 0 条回复

C C 普通 2024年3月5日上午8:10

# 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:
        nodeA, nodeB= headA, headB
        while nodeA != nodeB:
            nodeA = nodeA.next if nodeA else headB
            nodeB = nodeB.next if nodeB else headA
        return nodeA 

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

0 赞同 0 条回复

时生普通 2024年3月4日下午10:03

//先求出两条链表的长度之差num，再让长的链表先走num个结点，再同时向后遍历两条链表，并判断是否为同一个结点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
typedef struct ListNode ListNode;
ListNode *p = headA;
ListNode *q = headB;
int count1=0;
int count2=0;
while(p!=NULL){
p = p->next;
count1++;
}
while(q!=NULL){
q = q->next;
count2++;
}

 p = headA;
 q = headB;
 if(count1>=count2){
     int num = count1-count2;
     while(num!=0){
         p = p->next;
         num--;
     }
     while(p!=NULL){
         if(p == q){
             return p;
         }else{
             p = p->next;
             q = q->next;
         }
     }
 }
  if(count1<count2){
     int num = count2-count1;
     while(num!=0){
         q = q->next;
         num--;
     }
     while(p!=NULL){
         if(p == q){
             return p;
         }else{
             p = p->next;
             q = q->next;
         }
     }
 }
 return NULL;

}

0 赞同 0 条回复

小玉普通 2024年3月4日下午8:41

时间复杂度:O(n^2) 空间复杂度:O(1)
struct ListNode* getIntersectionNode(struct ListNode* headA,
                                     struct ListNode* headB) {
    typedef struct ListNode Node;
    Node *p = (Node*)malloc(sizeof(Node));
    Node *q = (Node*)malloc(sizeof(Node));
    p = headA;
    q = headB;
    if (p == NULL || q == NULL) // 边界情况
        return NULL;
    while (p != NULL) {
        q = headB;
        while (q != NULL) {
            if (p == q)
                return p;
            q = q->next;
        }
        p = p->next;
    }
    return NULL;
}

0 赞同 0 条回复

Yeah~ 普通 2024年3月4日下午4:48

/**
* 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(headAnullptr || headBnullptr) return nullptr;
int lenA = 0, lenB = 0;
ListNode A = headA;
ListNode* B = headB;
while(A != nullptr){
lenA++;
A = A->next;
}
while(B != nullptr){
lenB++;
B = B->next;
}
A = headA;
B = headB;
int diff;
if(lenA>lenB){
diff = lenA-lenB;
while(diff–){
A = A->next;
}
}else{
diff = lenB-lenA;
while(diff–){
B = B->next;
}
}

    while(A->val != B->val){
        A = A->next; 
        B = B->next;
        if(A == nullptr) break;
    }
    return A;
}

};
先统计长度差，长的先走两者相差的步数，接着两者同时向后并判断val，若相等则返回。
时间复杂度O(m+n)，空间O(1)
帅地的方法更优美

0 赞同 0 条回复

mpweixin用户普通 2024年3月4日下午4:39

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int s1=size(headA);
int s2=size(headB);
ListNode p1=headA;
ListNode p2=headB;
if(s10||s20) return null;
int d=s1-s2;
if(d>0){
while(d– >0) p1=p1.next;
}
else if(d<0){
d=-d;
while(d– >0) p2=p2.next;
}
while(p1!=p2){
p1=p1.next;
p2=p2.next;

    }
    return p1;
}
int size(ListNode head){
    int count=0;
    ListNode p=head;
    while(p.next!=null){
        count++;
        p=p.next;
    }
    return count;
}

思路：找出两个链表的长度差保证两个链表从同样的长度出发
时间O(n),空间O(1)
题解中有一个很6的思路是：两个指针一个先走a 然后走b 一个先走b再走a 指针相遇就是交点

0 赞同 0 条回复

阿野普通 2024年3月4日下午3:49

#打卡
/**
* 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 lA = 0, lB = 0, step = 0;
let nA = headA;
let nB = headB;
if(!nA || !nB) return null;
while (nA.next) {
lA++;
nA = nA.next;
}
while (nB.next) {
lB++;
nB = nB.next;
}
nA = headA;
nB = headB;
if (lA > lB) {
step = lA – lB;
for (let i = 0; i < step; i++) {
nA = nA.next;
}
} else if (lA < lB) {
step = lB – lA;
for (let i = 0; i < step; i++) {
nB = nB.next;
}
}
while (nA && nB) {
if (nA.val nB.val) return nA;
nA = nA.next;
nB = nB.next;
}
return null;
};

0 赞同 0 条回复

湘江小水鬼普通 2024年3月4日下午3:45

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode A = headA;
struct ListNode* B = headB;
while(A!=B){
A = A != NULL ? A->next : headB;
B = B != NULL ? B->next : headA;
}
return A;
}学习了双指针的方法，全部都走一遍，总会到固定的汇合点

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月4日上午11:09

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

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return nullptr;
        ListNode* curA = headA, *curB = headB;
        while(curA != curB) {
            curA = curA ? curA->next : headB; 
            curB = curB ? curB->next : headA;
        }
        return curA;
    }
};

0 赞同 0 条回复

一个达不刘普通 2024年3月4日上午9:46

思路：
AB同时走，A走完lengthA后，B还剩C-lengthA步。A再从B开始走，A走了C-lengthA步后，B到达A，此时AB同步。
举例：
A——3，B——4，C——1；
A走到null，B走到3.还剩1.此时A转向B。
向前一步，B走完，转向A，距离末端还剩3步，A此时走在了B1.距离末端还剩3步。此时AB同步，比较两个指针是否相同即可。

class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int skipA,skipB;
ListNode *A = headA, *B = headB;
while(A != B){
if(A != NULL){
A = A->next;
}else{
A = headB;
}
if(B != NULL){
B = B->next;
}else{
B = headA;
}
}
return A;
}
};

0 赞同 0 条回复

繁星普通 2024年3月3日下午10:40

方法一：先算长度，类似倒数第k节点
class Solution {
//时间复杂度O(n)，空间复杂度O(1)
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//先算两条链表的长度
int alength = getListNodeLength(headA);
int blength = getListNodeLength(headB);
//再让长的链表先走到和短链表一样长度的位置
ListNode curA = headA;
ListNode curB = headB;
int num = alength-blength;
if(num > 0) {
while(num > 0) {
curA = curA.next;
num–;
}
}else {
while(num < 0) {
curB = curB.next;
num++;
}
}
//同时走，若遇到相同的则是结果
ListNode res = null;
while(curA != null) {
if(curA curB) {
res = curA;
break;
}
curA = curA.next;
curB = curB.next;
}
return res;
}
//计算链表长度函数
int getListNodeLength(ListNode node) {
int length = 0;
ListNode cur = node;
while(cur != null) {
length++;
cur = cur.next;
}
return length;
}
}

方法二：转化成环的思路，速度一样，路程不一样相遇
class Solution {
//时间复杂度O(n),空间复杂度O(1)
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//A走完走B，B走完走A，相交
ListNode curA = headA;
ListNode curB = headB;
while(curA != curB) {
curA = curAnull?headA:curA.next;
curB = curBnull?headB:curB.next;
}
return curA;
}
}

0 赞同 0 条回复

东普通 2024年3月3日下午9:31

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int count = 0;
ListNode bighead = headA;
ListNode smhead = headB;
while (bighead!=null){
bighead = bighead.next;
count++;
}
while (smhead!=null){
smhead = smhead.next;
count–;
}
if (count > 0){
bighead = headA;
smhead = headB;
}else {
bighead = headB;
smhead = headA;
}
int aa = Math.abs(count);
while (aa>0){
bighead = bighead.next;
aa–;
}
while (bighead != null){
if (bigheadsmhead){
return bighead;
}
bighead = bighead.next;
smhead = smhead.next;
}
return null;
}
}
//先让链表长度长的先走m-n步

0 赞同 0 条回复

=.= 普通 2024年3月3日下午7:59

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

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

    return p1;
}

}

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

0 赞同 0 条回复

一颗红豆普通 2024年3月3日下午4:53

时间复杂度为O（m+n）即链表长度之和，空间复杂度为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 * A = headA;
ListNode *B = headB;
while(A!=B)
{
A= Anullptr?headB:A->next;
B = Bnullptr?headA:B->next;
}
return A;

};

0 赞同 0 条回复

一期一会普通 2024年3月3日下午3:58

同时遍历A和B，长度分别为a和b，A与B的相同节点长度为c，遍历结束后转为遍历另一链表，当访问至相同节点后输出。
时间复杂度为O(M+N),空间复杂度为O（1）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
        if(l1 == NULL) return l2;
        else if(l2 == NULL) return l1;
        else if(l1->val < l2->val)
        {
            l1->next = trainningPlan(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = trainningPlan(l1, l2->next);
            return l2;
        }

    }
};

0 赞同 0 条回复

Jankin 普通 2024年3月2日下午11:09

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

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

0 赞同 0 条回复

mpweixin用户普通 2024年3月2日下午10:22

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

刘超波普通 2024年3月2日下午10:19

提交/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode d1 = headA;
ListNode d2 = headB;
if (d1null||d2null) return null;
while (d1!=d2)
{
if (d1!=null)
{
d1 =d1.next;

    }else{
        d1 = headB;
    }
       if (d2!=null)
    {
        d2 =d2.next;
    }else{
        d2 = headA;
    }
    }


    return d1;

}

}

0 赞同 0 条回复

Augenstern 普通 2024年3月2日下午8:11

代码:public 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年3月2日下午7:25

class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode temp1=headA;
ListNode temp2=headB;
while((temp1!=null)||(temp2!=null))
{
if(temp1temp2)
return temp1;
if(temp1null)
temp1=headB;
else
temp1=temp1.next;
if(temp2null)
temp2=headA;
else
temp2=temp2.next;
}
return null;
}
}
两个变量分别从两个链表的起点进行第一次遍历，任何一方走到了null，就立刻换到另一个链表的起点进行第二次遍历，由于总的路程（两次遍历）是相同的，那么在这过程中碰到相同的节点就是相交节点，如果两次遍历都走完了还是没有找到相同的节点，那么就说明没有公共节点。
最差情况时间复杂度O(A+B)
空间复杂度O(1)

0 赞同 0 条回复

零普通 2024年3月2日下午7:24

思路：参考题解，属实没搞懂题意，这skip值不就用不到？？？
代码：

“`java
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (null == headA || null == headB) {
return null;
}
ListNode n1 = headA;
ListNode n2 = headB;
while (n1 != n2) {
n1 = n1 == null ? headB : n1.next;
n2 = n2 == null ? headA : n2.next;
}
return n1;
}

0 赞同 0 条回复

叫不醒装睡的人普通 2024年3月2日下午6:55

class Solution {
    // 两个链表不存在环
    // 找到两个链表的第一个公共节点，若没有则返回 null 
    // 利用两个指针分别指向两个链表
    // 对两个链表进行循环遍历，找到两个指针值相同的时候跳出循环
    // 当相对短的那个链表遍历结束后就去遍历另一个链表
    // 若两个链表不存在公共节点，则两个指针同时为 null 时跳出循环
    // 返回此时指针
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = A == null ? headB : A.next;
            B = B == null ? headA : B.next;
        }
        return A;
    }
    // 题解代码时间复杂度为 O(m + n)
    // 最差情况下，两个链表遍历完都没有公共节点
    // 空间复杂度为 O(1)，指针 A、B 占用额外空间为常数大小
}

0 赞同 0 条回复

mpweixin用户普通 2024年3月2日下午6:37

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 定义两个引用链表
        ListNode A = headA , B = headB; 
        while (A != B) {
            // A与B同时走，肯定会重合，如果重合的时为空，则无相交点，如果不为空则此值为重合的链表
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }


}

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

0 赞同 0 条回复

哆啦A梦的面包普通 2024年3月2日下午6:06

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

最差情况时间复杂度O(A+B)
空间复杂度O(1)

0 赞同 0 条回复

言之命至普通 2024年3月2日下午5:30

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遍历完，从headB链表开始走，否则往后遍历
            B = B == null ? headA : B.next;//如果B遍历完，从headA链表开始走，否则往后遍历
        }
//只要不指向同一个一直走，指向同一个的时候返回，A或B都可以
        return A;   
    }
}

最差情况时间复杂度O(A+B)
空间复杂度O(1)

0 赞同 0 条回复

lucky耶耶耶*👻*～普通 2024年3月2日下午5:29

//空间复杂度 O(1)时间复杂度 O(n)
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode A = pHead1;
        ListNode B = pHead2;
        while (A != B) {
            A = A == null ? pHead2 : A.next;
            B = B == null ? pHead1 : B.next;
        }
        return A;
    }
}

0 赞同 0 条回复

kfaebot 普通 2024年3月2日下午5:28

“`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) {
//分别定义遍历链表A和链表B的两个指针
ListNode *a=headA;
ListNode *b=headB;
while(a!=b){
//a遍历
if(a!=nullptr){
a=a->next;
}
else{
a=headB;
}
//b遍历
if(b!=nullptr){
b=b->next;
}
else{
b=headA;
}
}
//a和b相遇处即为所求
return b;
}
};
\\最差情况时间复杂度O(A+B)
\\空间复杂度O(1)
“`

0 赞同 0 条回复

😴 普通 2024年3月2日下午5: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) {
ListNode a = headA;
ListNode b = headB;
while(a != b){
a = a != null ?a.next: headB;
b = b != null ?b.next: headA;
}
//两个走的步数一样多，最后如果没有相同的结点指向，最后就是共同指向null
return null;

}
只想到了最简单的思路，通过长度来确定。
最优解很巧妙。
时间复杂度最好为(A+B-C)
最差为O（A+B）

0 赞同 0 条回复

Deckkker 普通 2024年3月2日下午5:09

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None

        A = headA
        B = headB
        while A != B:
            A = A.next if A else headB
            B = B.next if B else headA
        return A

分两种情况：
1、相交
两个链表有交点时，可以分为三部分，设交点为C
a:A链表到交点的节点数（不含交点C）
b:B链表到交点的节点数（不含交点C）
c:交点C到链表结束的节点数（含交点C）
A链表长为a+c
B链表长为b+c
当headA走完A链表，headB走完B链表，两个指针走过的节点数分别是a+c，b+c
若此时headA从链表B出发，headB从链表A出发，则两个节点在走到交点C时走过的步长分别为a+c+b，b+c+a,走过的节点数相等，步长一致的情况下，则说明同时到达交点C，此时返回任意一个指针即为交点C。

2、不相交
不相交可以看做是两个链表在None节点处相交，同样两个指针在遍历完A/B链表之后遍历B/A链表，指针在None节点交汇，则链表不相交。

时间复杂度O(A+B)：最差情况遍历两个链表
空间复杂度O(1)：常量空间

0 赞同 0 条回复

CurDei 普通 2024年3月2日下午5:06

通过总路程不变进行双向遍历
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A = headA, B = headB;
while(A != B){
A = A != null? A.next : headB;
B = B != null? B.next : headB;
}
return A;
}
}

0 赞同 0 条回复

ChenZhangHangTime 永久会员 2024年3月2日下午4:59

本题思路是A遍历完自己的链表之后就去遍历B链表，B遍历完自己的链表后就遍历A链表，假如他们两个是相交的话，那么一定会同时遍历到那个交点
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 条回复

　南木普通 2024年3月2日下午3:24

这道题学408的时候遇到过，结果又忘了，用了地哥的解法，真的优雅
时间复杂度O（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;
    }
}

0 赞同 0 条回复

NULL 普通 2024年3月2日下午2:59

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = 0, lenB = 0;
ListNode nodeA = headA, nodeB = headB;
while(nodeA!=null){
lenA++;
nodeA = nodeA.next;
}
while(nodeB!=null){
lenB++;
nodeB = nodeB.next;
}
nodeA = headA;
nodeB = headB;
if(lenB > lenA)return getIntersectionNode(headB,headA);
int distance = lenA – lenB;
for(int i = 0; i < distance; i++)nodeA = nodeA.next;//保证尾部对齐
while(nodeA != null){
if(nodeA nodeB)return nodeA;
nodeA = nodeA.next;
nodeB = nodeB.next;
}
return null;
}

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

0 赞同 0 条回复

墨丘俐普通 2024年3月2日下午2:22

/**
* 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 pointA = headA;
    ListNode pointB = headB;
    while(pointA!=pointB){
        if(pointA!=null){
            pointA = pointA.next;
        }else{
            pointA = headB;
        }
        if(pointB!=null){
            pointB = pointB.next;
        }else{
            pointB = headA;
        }



    }
    return pointA;

}

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

0 赞同 0 条回复

Laboratory 普通 2024年3月2日下午1:59

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 双指针，一个从A出发，一个从B出发
        ListNode cur1 = headA;
        ListNode cur2 = headB;

        while(cur1 != cur2) {
            cur1 = cur1 == null ? headB : cur1.next;
            cur2 = cur2 == null ? headA : cur2.next;
        }
        return cur1;
    }
}

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

0 赞同 0 条回复

普通 2024年3月2日下午1:45

class Solution {
public:
ListNode getIntersectionNode(ListNode *headA, ListNode *headB) {
int A_length=0,B_length=0;
ListNodep=headA; ListNode*q=headB;
while(p!=nullptr)
{
p=p->next;
A_length++;
}
while(q!=nullptr)
{
q=q->next;
B_length++;
}
int k=0; int AorB=1;
if(A_length>=B_length)
{ k=A_length-B_length; AorB=1; }
else { k=B_length-A_length; AorB=0; }

    while(k>0)
    {
        if(AorB==1 && headA != nullptr) headA=headA->next;
        if(AorB==0 && headB != nullptr) headB=headB->next;
        k--;
    }

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

};
打卡
时间复杂度为(O(m+n))，空间复杂度为(O(1))。

0 赞同 0 条回复

望普通 2024年3月2日下午1:43

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if headA is None or headB is None:
            return None
        ha, hb = headA, headB
        while ha != hb:
            if ha:
                ha = ha.next
            else:
                ha = headB

            if hb:
                hb = hb.next
            else:
                hb = headA

        return ha

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

0 赞同 0 条回复

mpweixin用户普通 2024年3月2日下午12:59

思路

浪漫的话母胎单身直男不多说，这个解法的本质是让两个指针在会合点前走到路程相等从而会合。

复杂度

时间复杂度:

O(M+N)

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

    }
}

0 赞同 0 条回复

Yuki 永久会员 2024年3月2日下午12:55

class Solution {
public:
ListNode getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNodepA=headA;
ListNode*pB=headB;
int lenA=0;
int lenB=0;

    while(pA!=NULL){
        pA=pA->next;
        lenA++;
    }
    while(pB!=NULL){
        pB=pB->next;
        lenB++;
    }

    if(lenA<lenB){
        swap(lenA,lenB);
        swap(headA,headB);//确保A更长
    }

    pA=headA;
    pB=headB;
    int gap=lenA-lenB;

    while(gap--){
        pA=pA->next;
    }
    while(pA!=NULL){
        if(pA==pB){
            return pA;
        }
        pA=pA->next;
        pB=pB->next;
    }
    return NULL;
}

};

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

0 赞同 0 条回复

持之以恒:-) 普通 2024年3月2日下午12:32

class Solution {
    /**
        1. 两个链表 两个指针，
        2. 根据链表长度来判断
        3. 长的先执行
    */
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode nodeA = headA;
        ListNode nodeB = headB;
        // 第一个公共
        int lenA = getListLen(nodeA);
        int lenB = getListLen(nodeB);

        // 还原数据
        nodeA = headA;
        nodeB = headB;
        int step = 0;

        step = lenA > lenB ? lenA - lenB : lenB - lenA;

        // 对齐 padding 
        if(lenA > lenB){
            while(step > 0){
                nodeA = nodeA.next;
                step--;
            }
        }
        else{
            while(step > 0){
                nodeB = nodeB.next;
                step--;
            }
        }

        // 两个链表对齐
        while(nodeA != null && nodeB != null && nodeA != nodeB){
            nodeA = nodeA.next;
            nodeB = nodeB.next;
        }
        if(nodeA == null || nodeB == null)
            return null;
        return nodeA;
    }

    private int getListLen(ListNode head){
        if(head == null)
            return 0;
        int len = 0;
        while(head != null){
            len++;
            head = head.next;
        }
        return len;
    }
}

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

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月2日下午12:18

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

    }
}

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

0 赞同 0 条回复

神经蛙普通 2024年3月2日下午12:05

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *n1 = headA;
struct ListNode *n2 = headB;
if(n1 NULL || n2 NULL){return NULL;}

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

return n1;

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

0 赞同 0 条回复

Bing0 普通 2024年3月2日上午11:47

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA == NULL || headB == NULL)
        return NULL;
    struct ListNode* A = headA;
    struct 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 条回复

！。！普通 2024年3月2日上午11:11

/**
* 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 curA = headA;
ListNode* curB = headB;
int a=0, b=0;
while(curA){
a++;
curA = curA->next;
}
while(curB){
b++;
curB = curB->next;
}
curA = headA, curB = headB;
if(a<b) swap(curA, curB);
for(int i=0; i<abs(a-b); i++){
curA = curA->next;
}
while(curA && curB){
if(curA->val curB->val) break;
curA = curA->next;
curB = curB->next;
}
return curA;
}
};
时间复杂O（A+B）空间复杂O（1）

0 赞同 0 条回复

Let it be 永久会员 2024年3月2日上午10:53

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（A+B）空间复杂O（1）

0 赞同 0 条回复

神经蛙普通 2024年3月2日上午10:35

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

        ListNode pa = headA, pb = headB;

        // 让A走B的路 B走A的路
        while(pa != pb){
            pa = pa == null ? headB : pa.next;
            pb = pb == null ? headA : pb.next;
        }

        return pa;

    }
}

0 赞同 0 条回复

30tcq 普通 2024年3月2日上午10:27

“`C++

//思路：双指针，ab同时遍历，然后去遍历对方，若相等，说明相遇
/**
* 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, *B;
A = headA, B = headB;
if(A NULL || B NULL) return NULL;
while(A != B){
A = A NULL ? headB : A->next;
B = B NULL ? headA : B->next;
}
return A;
}
};

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

0 赞同 0 条回复

HU 普通 2024年3月2日上午9:34

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

    // A == B的情况有两种
    // 情况一：链表不存在相交节点，A和B同为null
    // 情况二：链表存在相交节点，A和B同为相交节点
    while(A != B) {
        A = A == null ? headB : A.next;
        B = B == null ? headA : B.next;
    }

    return A;
};

0 赞同 0 条回复

mpweixin用户普通 2024年3月2日上午9:01

“`java
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;
}
}
“`java
时间复杂度O(M + N), 空间复杂度O(1)

0 赞同 0 条回复

Free 普通 2024年3月2日上午8:50

/**
 * 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 = 1, lenb = 1;
        ListNode* cura = headA, *curb = headB;
        while(cura)
        {
            lena++;
            cura = cura->next;
        }
        while(curb)
        {
            lenb++;
            curb = curb->next;
        }
        if(lena > lenb)
            swap(headA, headB);
        curb = headB, cura = headA;
        for(int i = 0; i < abs(lena - lenb); i++)
            curb = curb->next;
        while(cura && curb)
        {
            if(cura == curb)
                return cura;
            cura = cura->next;
            curb = curb->next;
        }
        return nullptr;
    }
};

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

0 赞同 0 条回复

Yox 普通 2024年3月2日上午4:08

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

class Solution:
def trainingPlan(self, head: Optional[ListNode], cnt: int) -> Optional[ListNode]:
count = 0
fast = head
slow = head
while count != cnt:
fast = fast.next
count +=1

    while fast != None:
        fast = fast.next
        slow = slow.next

    return slow

依旧很直接的解法，制造步数差然后遍历到尾部。记住返回节点而不是val。
时间o（N）无循环，空间o（1）常数空间

0 赞同 0 条回复

还不多喝热水普通 2024年3月2日上午12:23

/**
 * 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 tmpA = headA;
        ListNode tmpB = headB;
        // 两个节点地址不相等就继续遍历
        while (tmpA != tmpB) {
            tmpA = tmpA == null ? headB : tmpA.next;
            tmpB = tmpB == null ? headA : tmpB.next;
        }
        return tmpA;
    }
}

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

0 赞同 0 条回复

在线coding 普通 2024年3月1日下午11:38

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
class Solution {
/**
* 扫描三次链表，时间复杂度为O(n),空间复杂度固定了几个O(1)
*/
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA null || headB null){
return null;
}
int lenA = 0;
int lenB = 0;
ListNode tempA = headA;
ListNode tempB = headB;
//先遍历两次链表，分别得到链表的长度
while(tempA != null){
tempA = tempA.next;
++ lenA;
}
while(tempB != null){
tempB = tempB.next;
++ lenB;
}
//假如B链表长度大指针改一下减少下面代码重复性
if(lenB > lenA){
int tempLen = lenA;
lenA = lenB;
lenB = tempLen;
ListNode tempNode = headA;
headA = headB;
headB = tempNode;
}
//注意=
if(lenA >= lenB){
tempA = headA;
for(int i = 0; i < lenA – lenB; i ++){
tempA = tempA.next;
}
tempB = headB;
while(tempA != tempB){
tempA = tempA.next;
tempB = tempB.next;
}
return tempA;
}
return null;
}
}

0 赞同 0 条回复

统一绿茶Gin 普通 2024年3月1日下午11:30

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

Raphtalia. 普通 2024年3月1日下午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) {
// a长度为n，b长度为m，双指针同时走到尾，若为空返回到对方的头指针。
// 此时，若双方再相遇，则找到公共节点。
ListNode a = headA;
ListNode* b = headB;
while(a != b){ // 若ab同时为空，则公共节点为空
a = a ? a->next : headB;
b = b ? b->next : headA;
}
return a;
}
};
时间复杂度O（n+m），空间复杂度O（1）

0 赞同 0 条回复

while(1) 普通 2024年3月1日下午10:22

“`C++
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *A = headA, *B = headB;
while(A != B)
{
A = A != nullptr? A->next : headB;
B = B != nullptr? B->next : headA;
}
return A;
}
};
方法：双指针
时间复杂度：o(n)
空间复杂度：o(1)
如有问题，欢迎指正！

0 赞同 0 条回复

紫芝普通 2024年3月1日下午10:13

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

思路：分别计算出两个链表的长度，长的那个链表的头节点先前进长度差值diff步，然后两个链表一起前进，当遇到相同的节点时，则为两个链表的第一个相同节点。

“`C++
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA=0, lenB=0;
ListNode *curA = headA;
while (curA != nullptr) {
lenA++;
curA = curA->next;
}
ListNode *curB = headB;
while (curB != nullptr) {
lenB++;
curB = curB->next;
}
if (lenA < lenB) { curA = headA; headA = headB; headB = curA; int temp = lenA; lenA = lenB; lenB = temp; } int diff = lenA - lenB; while (diff > 0) {
diff–;
headA = headA->next;
}
while (headA && headB) {
if (headA->val == headB->val) break;
headA = headA->next;
headB = headB->next;
}
return headA;
}
};
“`

0 赞同 0 条回复

王位詮釋普通 2024年3月1日下午10:11

“`java
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode tempB = headB;
while(headA!=null){
while(tempB!=null){
if(headA==tempB){
return headA;
}
tempB = tempB.next;
}
tempB = headB;
headA = headA.next;
}
return null;
}
}
时间复杂度：O(n2)，直接暴力法做出来的，效率很差，没想到先算下两个长度然后遍历，看了其他学员的思路才知道了。

0 赞同 0 条回复

Jimmy 普通 2024年3月1日下午10:09

方法1：计算两个链表长度差值diff，让长链表先走diff，然后两个链表一起走，走到相同位置时返回此位置的节点

/**
 * 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 *dummyA = new ListNode(0);
        ListNode *dummyB = new ListNode(0);
        dummyA->next = headA;
        dummyB->next = headB;

        int sizeA=0,sizeB=0;
        while(dummyA->next != NULL){
            sizeA++;

            dummyA = dummyA->next;
        }

        while(dummyB->next != NULL){
            sizeB++;

            dummyB = dummyB->next;
        }

        ListNode *curA = headA;
        ListNode *curB = headB;
        int diff = abs(sizeA-sizeB);
        if(sizeA < sizeB){
            while(diff--){
                curB = curB->next;
            }
        }

        if(sizeA > sizeB){
            while(diff--){
                curA = curA->next;
            }
        }
        while(curA != NULL){
            if(curA == curB){
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};

方法2：走总路程，A走完了自己的路开始走B的路，B走完了自己的路开始走A的路。因为总路程是一样的，多走的路对方也要走，就总会走到同一起点。

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

0 赞同 0 条回复

机电皮怪永久会员 2024年3月1日下午9:34

时间复杂度o（n）
空间复杂度o（1）
###C++
”’
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
if ( head nullptr )
{
return nullptr;
}

    ListNode* dummyhead = new ListNode (999, head);
    ListNode* slow = dummyhead;
    ListNode* fast = dummyhead;
    for ( int i = cnt; i > 0; i-- )
    {
        fast = fast->next;
    }
    while( fast != nullptr )
    {
        fast = fast->next;
        slow = slow->next;
    }

    return slow;
}

};
”’

0 赞同 0 条回复

云无深雁影普通 2024年3月1日下午9:31

class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA null || headB null)
return null;
ListNode ptrA = headA;
int lenA = 0;
ListNode ptrB = headB;
int lenB = 0;
while(ptrA.next!=null){
lenA++;
ptrA = ptrA.next;
}

    while(ptrB.next!=null){
        lenB++;
        ptrB = ptrB.next;
    }
    if(ptrA != ptrB)
        return null;
    ptrA = headA;
    ptrB = headB;
    if(lenA > lenB)
        for(int i = 0; i < lenA - lenB; i++)
            ptrA = ptrA.next;
    else
        for(int i = 0; i < lenB - lenA; i++)
            ptrB = ptrB.next;
    do{
        if(ptrA == ptrB)
            return ptrA;
        ptrA = ptrA.next;
        ptrB = ptrB.next;
    }while(true);

}

}
两次遍历，第一次获得两条链表长度。第二次长链表指针先走长度之差步。
时间复杂度On
空间复杂度 O1

0 赞同 0 条回复

heathhou 普通 2024年3月1日下午9:21

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

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

        return A;
    }
};

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

0 赞同 0 条回复

是hua不是pua 普通 2024年3月1日下午9:17

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lengthA = getLength(headA);
        int lengthB = getLength(headB);
        System.out.println(lengthA);
        System.out.println(lengthB);
        int dis = lengthA > lengthB ? lengthA - lengthB : lengthB - lengthA;
        ListNode nodeL = lengthA > lengthB ? headA : headB;
        ListNode nodeS = lengthA > lengthB ? headB : headA;
        int i = 1;
        while(nodeL != null && i <= dis){
            nodeL = nodeL.next;
            i++;
        }
        while(nodeL != null && nodeS != null){
            if(nodeL.val == nodeS.val){
                return nodeL;
            }
            nodeL = nodeL.next;
            nodeS = nodeS.next;
        }
        return null;
    }

    int getLength(ListNode head){
        int length = 0;
        while(head != null){
            length++;
            head = head.next;
        }
        return length;
    }
}

双指针，day1打卡完毕

0 赞同 0 条回复

Monou 普通 2024年3月1日下午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 nodeA = headA;
ListNode nodeB = headB;
int numA = 0;
int numB = 0;
while(nodeA.next != null){
nodeA = nodeA.next;
numA ++;
}
while(nodeB.next != null){
nodeB = nodeB.next;
numB ++;
}
if(nodeA != nodeB){
return null;
}

    if(numA > numB){
        nodeA = headA;
        nodeB = headB;
    }else{
        nodeA = headB;
        nodeB = headA;
    }
    // nodeA 先走
    int num = Math.abs(numA - numB);

    while(num-- > 0){
        nodeA = nodeA.next;
    }

    while(nodeA != nodeB){
        nodeA = nodeA.next;
        nodeB = nodeB.next; 
    }
    return nodeA;


}

}
快慢指针

0 赞同 0 条回复

MARS 普通 2024年3月1日下午9:07

day1 打卡完毕，感觉还可以

var getIntersectionNode = function (headA, headB) {
    //先两条链表一起走完，记录步数，最后走完的节点一样，进入下一步，不一样直接return null
    let k = 0
    let cur1 = headA
    let cur2 = headB
    while (cur1) {
        cur1 = cur1.next
        k++
    }
    while (cur2) {
        cur2 = cur2.next
        k--
    }
    if (cur1 !<span class="text-highlighted-inline" style="background-color: #fffd38;"> cur2) return null<br />
    //最后节点一样 重新走
    cur1 = headA
    cur2 = headB
    if (k > 0) {   //让长的先走k步
        while (k--) {
            cur1 = cur1.next
        }
    } else {
        k =-k
        while (k--) {
            cur2 = cur2.next
        }
    }
    while (cur1 !</span> cur2 && cur1 && cur2) { //一起走，直到相等
        cur1 = cur1.next
        cur2 = cur2.next
    }
    return cur1
};

0 赞同 0 条回复

进取普通 2024年3月1日下午8:40

我吹过你吹过的晚风，那我们算不算相拥？

1 赞同 0 条回复

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

共以下 77 个回答

思路

复杂度

时间复杂度:

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

# 回答此问题取消回复

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

共以下 77 个回答

思路

复杂度

时间复杂度:

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

# 回答此问题 取消回复

# 回答此问题取消回复