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

lucca 普通 2022年12月30日上午1:33

拼接法

拼接的时候，以 $px != null$ 为分界线，否则循环无法停止

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        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;
    }
}

0 赞同 0 条回复

糖鑫普通 2022年12月2日上午12: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) {
        //两个指针分别从两个头节点出发，同速度，其中一个到达终点后从另一头节点重新出发，直到两节点相遇，相遇节点即公共节点
        //公共节点前的长度分别为a,b，公共长度c，两指针同速前进，要相遇的充要条件是走的距离相同，则同走了a+c+b
        /*其实这道题关键就是如果把握两个指针，比较两条道路不一样长，把控
        他们速度在公共节点相遇实属不易。所以两个问题
        ** 1：路不一样长， 2：两指针速度把控**
        路不一样长，就拼接一起，搞一样长，速度不一样就搞成一样*/
        if(headA==null||headB==null){return null;}
        ListNode a=headA;
        ListNode b=headB;
        while(a!=b){
            /*改变原有结构造出了环，所以超出时间
            if(a.next==null){
                a.next=headB;
            }
            if(b.next==null){
                b.next=headA;
            }*/
            /*多走了一步? =同一循环内指针速度不一致
            if(a==null){
                a=headB;
            }
            if(b==null){
                b=headA;
            }
            a=a.next;
            b=b.next;*/
            a= a==null?headB:a.next;
            b= b==null?headA:b.next;
        }
        return a;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2022年11月20日上午10:07

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        # write code here
        p1 = pHead1
        p2 = pHead2
        # 遍历
        # 有公共点时，p1和p2一定相遇，当p1 = p2就是公共节点
        # 没有公共点时，p1和p2走到终点null
        while p1 != p2:
            # p1从1遍历再去遍历2
            p1 = p1.next if p1 else pHead2
            # p2从2遍历再去遍历1
            p2 = p2.next if p2 else pHead1
        return p1

时间复杂度：O(m+n) 两个链表长度之和
空间复杂度：O(1)

0 赞同 0 条回复

格格巫普通 2022年11月19日下午6:25

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    if(headA == null || headB == null){
        return null;
    }

    let tempA = headA; 
    let tempB = headB;
    while(tempA !== tempB){
        tempA = (tempA !== null)? tempA.next : headB;
        tempB = (tempB !== null)? tempB.next : headA; 
    } 
    return tempA;
};

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

0 赞同 0 条回复

PatNick 普通 2022年11月13日下午2:52

def getInterssectionNode(headA:ListNode,headB:ListNode)->ListNode:
    '''
    方法1：求两个链的长度差，让长的先走"长度差"步，此时两个指针在同时走就是相当于在两个链尾部对其的情况下在同时走
    方法2：因为是单链条（a，b）有相交，所以如果有两个指针x，y，一个指针先走a个节点再走b个节点，另一个指针先走b个节点再走a个节点
    两个指针的总路长是一样的（两条路径一定数量是对其的，因为长度一样，而且a和b又有重合的部分，所以两条对其的路后面几个节点是重合的），所以一定会在某个节点相遇后，后面的节点一直重合
    例如：输入intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
    指针a走：09124324
    指针b走：32409124
    倒数的2就是相交的节点
    这里实现方法2
    Args:
        headA:
        headB:

    Returns:

    '''
    if (not headB) or (not headA):
        return None
    first = headA
    second = headB

    while first != second:
        # 说明此时a链已经走完了，但还没有找到交点，就换b链走
        # if not first:
        #     first = headB
        # # 说明此时b链已经走完了，但还没有找到交点，就换a链走
        # elif not second:
        #     second = headA
        # else:
        #     first = first.next
        #     second = second.next

        first = first.next if first else headB
        second = second.next if second else headA

    return first

0 赞同 0 条回复

hmmm 普通 2022年10月30日下午9:25

“`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 *p = new ListNode(-1);
ListNode *q = new ListNode(-2);
p = headA;
q = headB;

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

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

0 赞同 0 条回复

叶页耶夜烨邺普通 2022年10月28日下午6:27

时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 *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return nullptr;
        ListNode* currA = headA;
        ListNode* currB = headB;
        while(currA != currB){
            currA = currA == nullptr ? headB : currA->next;
            currB = currB == nullptr ? headA : currB->next;
        }
        return currA;
    }
};

0 赞同 0 条回复

和普通 2022年10月27日下午5:38

 ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //其中有一个是空就没有公共交点
        if (headA == null || headB == null) {
            return null;
        }
        //为了不改变headA和headB，所以新定义两个。
        ListNode first = headA;
        ListNode third = headB;
        while (first != third) {
            if (first == null) {
                first = headB;
            } else if (third == null) {
                third = headA;
            } else {
                first = first.next;
                third = third.next;
            }
        }
        return first;
    }

0 赞同 0 条回复

。。。。普通 2022年10月27日下午3:29

时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 *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if(headA==nullptr||headB==nullptr) return NULL;
    ListNode* m=headA;
    ListNode* n=headB;
    while(m!=n){
        m=m==nullptr? headB:m->next;
        n=n==nullptr? headA:n->next;
    }
    return m;
    }
};

0 赞同 0 条回复

Xiao 普通 2022年10月26日下午6:05

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

        while(A != B){//A不等于B，A,B都往下遍历
            A = A == null ? headB : A.next;
            B = B == null ? headA : B.next;
        }

        return A;
    }
}

0 赞同 0 条回复

小趴菜永久会员 2022年10月26日上午12:38

时间o（m+n）；空间o（1）
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1=headA;
ListNode p2=headB;
while(p1!=p2){
if(p1null){
p1=headB;
}
else{
p1=p1.next;
}
if(p2null){
p2=headA;
}
else{
p2=p2.next;
}
}
return p2;
}
}

0 赞同 0 条回复

努力刷题普通 2022年10月25日上午7:25

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        pa, pb = headA, headB
        while pa != pb:
            pa = pa.next if pa else headB
            pb = pb.next if pb else headA
        return pa
时间复杂度O（m+n)
空间复杂度O（1）

0 赞同 0 条回复

韩杰普通 2022年10月24日下午8:53

1,其实就是创建两个指针，分别遍历两个链表，每个指针遍历完自己的链表后再遍历另一个链表，如果链表后有重合的部分，而每个指针除了走过重合的部分外，其实分别走了一下没重合的链表部分，所以当两个指针走完之后，必为重合的那个节点。若无重合部分，两指针会指向空。
2，时间复杂度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) {
        ListNode A = headA,B = headB;
        while(A!=B){//疑问，若是公共节点之前又相同的节点不会误判吗？应该不会误判，这应该和ListNode A   这个有关现在还不太懂
            A = A != null ? A.next :headB;
            B = B != null ? B.next :headA;
        }

        return A;
    }
}

0 赞同 0 条回复

刺猬普通 2022年10月24日上午11:20

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

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

0 赞同 0 条回复

🚲南下普通 2022年10月24日上午9:59

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

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* A = headA;
        ListNode* B = headB;
        if(A==nullptr || B==nullptr){ //有一个为为空则直接返回
            return NULL;
        }
        while(A!=B){  
            A=A==nullptr?headB:A->next;//A到末尾则定位到B的头节点
            B=B==nullptr?headA:B->next;//B同上，直到相遇
        }
        return A;
    }
};

0 赞同 0 条回复

cute. 普通 2022年10月24日上午8:57

思路：
哈希表解法:哈希表的方式就是遍历链表a并且把每个节点存入到哈希表中，在遍历链表b的时候去哈希表中取，如果有存在于哈希表中就找到了第一个公共节点
因此使用双指针法进行解决

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

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

0 赞同 0 条回复

啊哈普通 2022年10月24日上午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) {

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

        ListNode* A = headA;
        ListNode* B = headB;

        //当A B走都走过重合的部分，相遇
        while(A != B){
            A = A == NULL ? headB : A -> next;
            B = B == NULL ? headA : B -> next;
        }
        return A;
    }
};

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

0 赞同 0 条回复

阿白普通 2022年10月23日下午11:55

1、只要存在公共节点，那么a走完接着去走b，b走完接着去走a，他们一定会相遇。（本质原因还是说不太清）
2、时间复杂度O（n+m），空间复杂度O（1）

struct ListNode
{
    ListNode *next;
    int val;

};

ListNode *meetNList(ListNode *headA, ListNode* headB)
{
    if (headA == nullptr || headB == nullptr) return nullptr;
    ListNode *A = headA;
    ListNode *B = headB;

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

    }
    return A;
}

0 赞同 0 条回复

优秀市民普通 2022年10月23日下午11:50

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

    }
}

时间复杂度o(m+n)
空间复杂度o(m)
俩个链表不停的去走互相走过对方的位置就可以找到相交的节点

0 赞同 0 条回复

symbol 普通 2022年10月23日下午9:23

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    temp := map[*ListNode] bool{}
    for t:= headA;t != nil;t=t.Next{
        temp[t] = true
    }
    for t:= headB;t != nil;t=t.Next{
        if temp[t]{
            return t
        }
    }
    return nil
}

1、遍历第一个链表,存入一个容器中,在遍历第二个链表,如果节点在容器中已经存在,则从该节点开始往后是两个链表的重复部分
2、时间复杂度：O(m+n)，其中 m 和 n 是分别是链表 headA 和 headB 的长度。需要遍历两个链表各一次。
空间复杂度：O(m)，其中 m 是链表 headA 的长度。需要使用哈希集合存储链表 headA 中的全部节点。

0 赞同 0 条回复

cxc 普通 2022年10月23日下午8:23

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

Ruby🗽 普通 2022年10月23日下午6:21

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

时间复杂度 n
空间复杂度 1

0 赞同 0 条回复

Gg 普通 2022年10月23日下午5:50

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;
        while(p1 != p2){
            // A链表不同部分为a，B链表不同部分为b，相同部分为c。让两指针同时走a+b+c步，节点相同则相交
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA : p2.next; 
        }
        return p1;
    }
}

0 赞同 0 条回复

云雾里普通 2022年10月23日下午5:12

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

0 赞同 0 条回复

just 普通 2022年10月23日下午4:31

//双指针？
class Solution {
public:
int fun(ListNode* head){
if(!head) return 0;
return 1+fun(head->next);
}
ListNode getIntersectionNode(ListNode *headA, ListNode *headB) {
int numa=fun(headA);
int numb=fun(headB);
if(numb>numa){
swap(numa,numb);
swap(headA,headB);
}
int sub=numa-numb;
ListNode a=headA,* b=headB;
while(sub–) a=a->next;
while(a){
if(ab) return a;
a=a->next;
b=b->next;
}
return nullptr;
}
};

0 赞同 0 条回复

@ 普通 2022年10月23日上午11:32

看了一下双指针题解，确实简单，奈何我想不到

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

0 赞同 0 条回复

YZ 普通 2022年10月23日上午9:39

class Solution {
    //1.第一次写的时候不太了解双指针，使用暴力枚举法，看了题解，发现双指针非常巧妙，非常优雅
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;   //当A遍历到NULL时，将headB接到A上
          B = B==NULL?headA:B->next;   //当B遍历到NULL时，将headA接到B上
      }                                //用这两个语句将步距磨平，使A和B在同一结点上比较，如果地址相同，即为所求公共节点                            //也可以这么理解，长短链表除去公共部分相差k,让他们互相连上各自的链表，长链表接上短链表，短链表接上长链表，两个指针的步子相同，如果地址相同，即为所求的第一个公共结点
      return A;                        
    }
};

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

0 赞同 0 条回复

浅夏的无奈普通 2022年10月23日上午9:09

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //创建两个辅助节点
        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 条回复

-辰华- 永久会员 2022年10月23日上午12:54

/**
 * 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) {
        // 如果有一个链表为空，返回null
        if (headA == null || headB == null) return null;
        ListNode a = headA, b = headB;
        // 分别遍历两个链表，若遍历到节点为null，则遍历另一个链表，直到节点相交
        while (a != b) {
            a = a == null? headB: a.next;
            b = b == null? headA: b.next;
        }
        return a;
    }
}

时间复杂度：O(m+n),其中m,n分别为链表的长度
空间复杂度：O(1)

0 赞同 0 条回复

yanshuojune 普通 2022年10月23日上午12:25

解体思路：使用双指针分别指向两个链表，循环完自己链表后指向另一个链表的head，当对应val相等时，此时两指针相遇，得到公共节点
时间复杂度：O(m+n),每个指针都遍历了链表1+链表2
空间复杂度：O(1)

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

0 赞同 0 条回复

mpweixin用户永久会员 2022年10月22日下午11:47

public class Solution {
    public 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(n+m)
空间复杂度：O(1)

0 赞同 0 条回复

糖香香普通 2022年10月22日下午11:04

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

0 赞同 0 条回复

Tolkien 永久会员 2022年10月22日下午10:43

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

 ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 判断特殊情况，其中一个链表为空，则返回空
        if (headA == null || headB == null) {
            return null;
        }

        // 两个链表分别遍历，若遍历到空，则继续遍历另一个链表，直到两个节点相同
        // 原理 A: 1 2 3 8 6 null, B: 0 2 4 6 8 6 null
        // 1 2 3 8 6 null 0 2 4 6 8 6 null
        // 0 2 4 6 8 6 null 1 2 3 8 6 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 条回复

MR.SandMan 普通 2022年10月22日下午10:12

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

两个链表合起来遍历

0 赞同 0 条回复

波波_1936 普通 2022年10月22日下午9:11

    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null) return null;
        ListNode nodea = headA;
        ListNode nodeb = headB;
        while (nodea!=nodeb){
            if (nodea!=null){
                nodea = nodea.next;
            }else {
                nodea = headB;//相当于从A到B组成了一个环，
            }
            if(nodeb!=null){
                nodeb=nodeb.next;
            }else {
                nodeb = headA;//同理
            }
        }
        // return a b都行，因为是同一个节点
        return nodea;

    }

时间复杂度O(N+M) n m分别是链表长度
空间复杂度为O(1)

0 赞同 0 条回复

Magi 普通 2022年10月22日下午9:08

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
         //老规则，先判断特殊情况
        if (headA == null || headB == null) {
            return null;
        }

        //定义两个指针
        ListNode A = headA;
        ListNode B = headB;

        //循环链表，如果A（B）走到末尾则继续走headB（headA）链表，直到相交
        //相交最后一个结点的下一个节点为虚拟的空结点
        //第一次错误的原因：while写成if
        while(A!=B)
        {
            A = A==null?headB:A.next;
            B = B==null?headA:B.next;
        }
        return A;
    }

0 赞同 0 条回复

你有点可爱喔普通 2022年10月22日下午9:02

时间复杂度O(m+n)

 ListNode getIntersectionNode(ListNode headA, ListNode headB) {
          //思路1：蛮力法
          //思路2：双栈
          //思路3：先遍历较长的链表，以及求出链表比短链表多几个节点
           int lengthA = 0;
           int lengthB = 0;
           ListNode tempA = headA;
           ListNode tempB = headB;
           while(tempA!=null){
               lengthA++;
               tempA = tempA.next;
           }
           while(tempB!=null){
               lengthB++;
               tempB = tempB.next;
           }
       //    int lengthDif = lengthA-lengthB;
          // ListNode shortNode = headA;
           //ListNode longNode = headB;
           tempA = headA;
           tempB = headB;


            if(lengthB<lengthA){
                while(lengthA!=lengthB){
                    tempA = tempA.next;
                    lengthA--;
                }
            }
           if(lengthB>lengthA){
               while(lengthA!=lengthB){
                   tempB = tempB.next;
                    lengthB--;
               }
            }
            while(tempA!=null){
                if(tempA==tempB){
                    return tempA;
                }
                tempA = tempA.next;
                tempB = tempB.next;
            }
            return tempA;
            //    longNode = headB;
            //    shortNode = headA;
            //    lengthDif = lengthB-lengthA;

        //    for(int i =0;i<lengthDif;++i){
        //        longNode = longNode.next;
        //    }
        //    while((longNode!=null)&&(shortNode!=null)&&(longNode!=shortNode)){
        //        longNode=longNode.next;
        //        shortNode=shortNode.next;
        //    }
        //    ListNode sectionNode = longNode;
        //    return sectionNode;

    }

0 赞同 0 条回复

晨普通 2022年10月22日下午8:43

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        #判空
        # if not headA and headB:
        #     return null
        #初始化
        A = headA
        B = headB
        #循环链表，如果A（B）走到末尾则继续走HeadB（HeadA）链表，知道相交
        while A != B:
            A = A.next if A else headB
            B = B.next if B else headA
        return A

0 赞同 0 条回复

Monster Dump 普通 2022年10月22日下午8:20

代码实现 (Java)

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

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

0 赞同 0 条回复

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

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //设交集链表长c,链表1除交集的长度为a，链表2除交集的长度为b，有
        //a + c + b = b + c + a
        //若无交集，则a + b = b + a


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

cxxz 普通 2022年10月22日下午8:05

看了视频学到了思路，使用两个指针遍历两个链表，如果访问到了null节点，就接着访问另一条链表，相当于是6+4+null=4+6+null的感觉，各走相同的路一定能找到相交处，找不到就是一起走到了null（也相等了），返回就行。

ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if (pHead1 == nullptr || pHead2 == nullptr)
            return nullptr;

        ListNode* fir, *sec;
        fir = pHead1;
        sec = pHead2;
        while ( fir != sec)
        {
            if (fir == nullptr)
                fir = pHead2;
            else
                fir = fir->next;
            if (sec == nullptr)
                sec = pHead1;
            else
                sec = sec->next;
        }
        return fir;
    }

时间复杂度O(m+n)
空间复杂度O(1)
压哨打卡（：

0 赞同 1 条回复

cxxz 普通 @ cxxz 2022年10月22日下午8:06

注意访问到null节点直接赋值，不要再使用->next了。

登录以回复

泡芙永久会员 2022年10月22日下午7:31

思路：遍历完链表 A 之后开始遍历链表 B，遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起
时间复杂度：O(a + b)
空间复杂度：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 条回复

酥合普通 2022年10月22日下午7:16

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

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

0 赞同 0 条回复

绍熙普通 2022年10月22日下午6:47

思路：双指针暴力解

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

0 赞同 0 条回复

lone。普通 2022年10月22日下午6:24

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //判断为null的情况
        if (headA == null || headB == null) {
            return null;
        }

        // A B 差异节点为 c  A总节点为 a+c  B总节点为 b+c
        //当存在公共节点 且是头节点直接返回
        //不是头节点 指针A走至A链表结束，指针B还未结束，将指针A置为链表B，指针B结束置为链表A
        //若存在公共节点即会相遇，所走路程 为 a+c+b = b+c+a
        //不存在，所走路程皆为 a+c+b+c (两个链表长度之和) 返回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 条回复

溴麝香草酚蓝普通 2022年10月22日下午5:48

思路
1. 通过双指针(curA,curB)分别遍历两个链表,保证两个指针经过的节点数一致,即经过一次完整遍历后,两个指针要么指向同一个节点,要么指向null
2. 当两个指针指向同一个节点(或是都为null)时,即完成遍历,返回任意一个指针指向的节点即可
代码

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

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

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

0 赞同 0 条回复

小肸永久会员 2022年10月22日下午3:58

思路一：先遍历一个链表，将遍历的节点加入到集合中，再开始遍历第二个链表，第一次在集合中出现的节点就是两个链表的第一个公共节点。时间复杂度O（N），空间复杂度O（N)。
思路二：统计两个链表的长度，让长链表先走两个链表长度的差值步，然后和短链表一起走，边走边判断两个链表的节点值是否相等，相等的节点就是两个链表的第一个公共节点。时间复杂度O(N)，空间复杂度O(1)。
思路三：双指针法。有链表A、链表B，指针pa指向A的头节点，指针pb指向B的头节点，两个指针每一次都往后走一步，当指针pa走完链表A后，从链表B的头节点走。指针pb同理，直到pa和pb指向的两个节点相同就是两个链表的第一个公共节点。给出简单证明：链表A的头节点距第一个公共节点有a步，链表B的头节点距第一个公共节点有b步，第一个公共节点距尾节点有k步，如果a=b，那么pa，pb的第一次遍历就找到公共节点。如果a!=b，那么pa走a+k+b步，pb走b+k+a步，这时两个指针也到第一个公共节点。时间复杂度O(N)，空间复杂度O(1)。
给出双指针法的实现

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

0 赞同 0 条回复

Y7n05h 普通 2022年10月22日下午3:45

题解

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

0 赞同 0 条回复

晨渊普通 2022年10月22日下午3:15

//思路：法1：统计链表长度，较长的先走N步，时间复杂度o(n+M)
//法2:两个链表逆置，从后向前比较，找到最后一个相同节点,
 //法3:两链表的头指针同时出发，当链表为空时，接上遍历另外一条链表，（相当于磨平了步矩，类似于法1），当第二次经过第一个公共节点时，就是相遇。
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;//A走完后，从headB再走一遍
           else  A=A->next;

            if(B==NULL) B = headA;//B走完后，从headA再走一遍
             else  B=B->next;
        }
        return A;

    }
};

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

0 赞同 0 条回复

T 普通 2022年10月22日下午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) {

        ListNode A = headA;
        ListNode B = headB;
        // A步数 + 公共C + B步数 = B步数 + 公共C  + A步数
        while(A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }
}

0 赞同 0 条回复

追普通 2022年10月22日下午2:21

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

注意：当链表A的指针到链表A结尾时，则接着指向链表B的头节点的语法

0 赞同 0 条回复

xye 普通 2022年10月22日下午2:16

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil{
        return nil
    }

    nodeA,nodeB := headA,headB
    for nodeA != nodeB {
        if nodeA == nil{
            nodeA = headB
        }else{
            nodeA = nodeA.Next
        }
        if nodeB == nil {
            nodeB = headA
        }else{
            nodeB = nodeB.Next
        }
    }
    return nodeA
}

以上双链表，利用a+b+c

0 赞同 0 条回复

潜行1 我是火车王！普通 2022年10月22日下午2:02

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

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }

    curA, curB := headA, headB
    for curA != curB {
        // 修改这里的条件为 headA应该可以应用于成环的链表
        if curA == nil {
            curA = headB
        } else {
            curA = curA.Next
        }

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

    return curA
}

0 赞同 0 条回复

Haoyun 普通 2022年10月22日下午1:55

遍历链表headA,将其每个节点加入哈希表中，然后遍历链表B，判断节点是否在哈希集合中
时间复杂度：O(m+n)
空间复杂度：O(m)

var getIntersectionNode = function(headA, headB) {
    const set=new Set();
    let cur=headA;
    while(cur){
        set.add(cur);
        cur=cur.next;
    }
    cur=headB;
    while(cur){
        if(set.has(cur)){
            return cur;
        }
        cur=cur.next;
    }
    return null;
};

0 赞同 0 条回复

庄重普通 2022年10月22日下午12:31

//思路1：
// 1.计算两个链表长度差
// 2.长的链表先走，至和短的链表长度相等，
// 3.之后同时遍历，找到相同地址的节点
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //不能判断两个节点的值相等，应该判断地址是否相等
         if(headA == NULL || headB == NULL) return NULL;
         //需要增加一组临时变量，否则第二次遍历的时候headA或者headB，会变成空指针
         ListNode* ATmp = headA;
         ListNode* BTmp = headB;

         int Alen = 0 ,Blen = 0;
         for(;ATmp != NULL;++Alen){
             ATmp = ATmp->next;
         }
         for(;BTmp != NULL;++Blen){
             BTmp = BTmp->next;
         }
         //遍历到同一位列
         for(int i = 0;iBlen)
                headA = headA->next;
            else
                headB = headB->next;
         }
        //走完剩下的路
         for(; headA !=headB;){
             headA = headA->next;
             headB = headB->next;
         }
         return headA;
        // for(; headA != NULL;){
        //     if(headA == headB)
        //         return headA;
        //     headA = headA->next;
        //     headB = headB->next;
        // }
        // return NULL;
    }
};
//时间复杂度O(m+n) (m+n)为两个链表长度之和
//空间复杂度O(1)

// 思路2：len: headA > headB
// 1.headA走了 A的长的部分+公共部分+B的短的部分 
// 2.headB走了 B的短的部分+公共部分+A的长的部分 
// 3.从而会在公共节点处相遇
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == NULL || headA == NULL) return NULL;

        ListNode* A_B = headA;
        ListNode* B_A = headB;

        for(; A_B != B_A;){
            A_B = A_B == NULL ? headB : A_B->next;
            B_A = B_A == NULL ? headA : B_A->next;
        }
        return A_B;
    }
};
// 时间复杂服O(m+n) 遍历了两个链表的长度，时间复杂度和思路1一样
// 空间复杂度O(1)

0 赞同 0 条回复

虾仁猪心普通 2022年10月22日下午12:30

思路：本题时快慢指针的变体，先让长的链表提前走（长链表长度-短链表长度）步，
然后两个链表一起遍历，当遍历到值相同的节点时返回，此时时第一个公共节点。
1. 写一个循环遍历函数findListLength（ListNode l）；返回值是int，用于返回链表长度。
2. 写一个move函数，参数1是长的链表，参数2是短的链表，参数3是长链表的长度，参数4是短链表的长度，长度用于计算快指针提前走几步，move函数内的任务和前面Offer22中的内容相似，快指针提前走了几步以后，快慢指针再一起遍历。
3. 用Step1中得到的链表长度判断输出进来的两个链表谁长，根据长度来决定调用step2中move函数的参数位置。
4. 返回
时间复杂度O(n)
空间复杂度O(1)

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int p1 = ListLength(pHead1);
        int p2 = ListLength(pHead2);
        ListNode res = null;
        if(p1>=p2){
            res = Move(pHead1,pHead2,p1,p2);   
        }else{
            res = Move(pHead2,pHead1,p2,p1);
        }
        return res;


    }
    public ListNode Move(ListNode fast,ListNode slow,int fastL,int slowL){
        int n = fastL-slowL;
        for(int i=0;i<n;i++){
            fast = fast.next;
        }
        while(fast!=null && slow != null && fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;

    }
    public int ListLength(ListNode list){
        int n =0;
        ListNode cur = list;
        while(cur!=null){
            n++;
            cur = cur.next;
        }
        return n;
    }
}

0 赞同 0 条回复

是梦终空永久会员 2022年10月22日下午12:25

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

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

0 赞同 0 条回复

派大星普通 2022年10月22日下午12:04

//时间复杂度O(n^2)
//空间复杂度O(1)
public class Solution {
    public ListNode findNode(ListNode f1,ListNode f2){
        if(f1==null||f2==null) return null;
        ListNode temp1 = f1;
        ListNode temp2 = f2;
        for(;temp1 != null;temp1=temp1.next){
            for(;temp2 != null;temp2=temp2.next){
                if(temp1==temp2){
                    return temp1;
                }
            }
        }

        return null;
    }
}

0 赞同 0 条回复

wxc 普通 2022年10月22日上午11:18

额

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

0 赞同 0 条回复

单个酒窝儿普通 2022年10月22日上午10:44

我再去看几遍

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

mpweixin用户普通 2022年10月22日上午10:32

示例1中两个链表的1是val，是值相同，地址不同。一开始还在想为什么1没相交。直接找。

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 ? headB : p.next;
            q = q == null ? headA : q.next;
        }
        return p;
    }
}

0 赞同 0 条回复

Asphyxia 普通 2022年10月22日上午9:52

快慢指针先判断有环没，并且记录第一次相遇地点；然后有环的话fast从头结点一步步走,low继续走，检查相遇节点

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* fast=pHead;
        ListNode* low=pHead;
        while(fast!=NULL&&fast->next!=NULL){
            fast = fast->next->next;
            low = low->next;
            if(fast==low){
                break;
            }
        }
        if(fast==NULL||fast->next==NULL){
            return NULL;
        }
        //there is a ring
        fast=pHead;
        while(fast!=low){
            fast = fast->next;
            low = low->next;
        }
        return low;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2022年10月22日上午9:29

/**
 * 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;
        int a_len = 0;
        int b_len = 0;
        while(A != null){
            a_len++;
            A = A.next;
        }
        while(B != null){
            b_len++;
            B = B.next;
        }
        A = headA;
        B = headB;
        if(a_len >= b_len){
            for(int i = 0; i < a_len - b_len; i++){
                A = A.next;
            }
        }else{
            for(int i = 0; i < b_len - a_len; i++){
                B = B.next;
            }
        }
        while(A != B){
            A = A.next;
            B = B.next;
        }
        return A;
    }
}

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

0 赞同 0 条回复

乱世枭雄普通 2022年10月22日上午9:05

思路：
链表节点相等，即为二者地址相同而非所存数值相同
若两个链表存在公共节点，可以依次遍历比较节点是否相等
两个链表除去公共部分可能一长一短，所以遍历两次，长+公共+短=短+公共+长之后首次相遇即为首个公共节点

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

黎昕普通 2022年10月22日上午1:33

遍历+第二次遍历使用快慢指针

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
       //遍历+第二次遍历使用快慢指针
       ListNode* pa=headA;
       int lena=0;
       while(pa!=NULL){
           lena++;
           pa=pa->next;
       } 
        ListNode* pb=headB;
       int lenb=0;
       while(pb!=NULL){
           lenb++;
           pb=pb->next;
       } 
       //printf("%d %d",lena,lenb);
       pa=headA;
       pb=headB;
       if(lena>=lenb){
           int delta=lena-lenb;
            for(int i=0;i<delta;i++){
                pa=pa->next;
            }
            while(pa!=pb&&pa!=NULL&&pb!=NULL){
                pa=pa->next;
                pb=pb->next;
            }
       }else{
           int delta=lenb-lena;
            for(int i=0;i<delta;i++){
                pb=pb->next;
            }
            while(pa!=pb&&pa!=NULL&&pb!=NULL){
                pa=pa->next;
                pb=pb->next;
            }
       }
       return pa;  
    }
};

0 赞同 0 条回复

星河普通 2022年10月22日上午12:43


```
//方法一，快慢指针
//第一遍遍历，求两个链表长度n1，n2
//第二遍遍历，较长的链表指针先走n2-n1步，然后两个链表的指针同时向前走
//时间O(N)，空间O(1)
//方法二，两指针同时走
//A把自己的路走完后走了一段B的路，B也是这样，所以各走了一圈半左右
class Solution {
    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(n)，空间O(1)
```

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月22日上午12:27

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

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null||headB == null) return null;//如果存在一个为null则公共节点不存在
        ListNode nodeA = headA;
        ListNode nodeB = headB;
        //设交集链表长c,链表1除交集的长度为a，链表2除交集的长度为b，有
        // a + c + b = b + c + a
        //使用的原理是，假设A的长度为n，B的长度为m，两者只要有共同节点，就会在m + n次遍历中遇上
        //都为null时是m+n次遍历，说明不存在共同节点了
        while(nodeA != nodeB){
            nodeA = nodeA == null ? headB : nodeA.next;
            nodeB = nodeB == null ? headA : nodeB.next;
        }
        return nodeA;
    }
}

0 赞同 0 条回复

Chin 普通 2022年10月22日上午12:11

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

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

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

0 赞同 0 条回复

马啸天永久会员 2022年10月22日上午12:08

public class Solution {
    ListNode getIntersectionNode(ListNode headA , ListNode headB) {
        //没有思路，看的解题，一个人走3步，一个人走4步，他们两个可以互相加一下，就是共同走7步，

        if (headA == null || headB == null)
            return null;
        ListNode node1 = headA;
        ListNode node2 = headB;
        while (node1 != node2) {
            node1 = (node1 == null ? node2 : node1.next);
            node2 = (node2 == null ? node1 : node2.next);
        }
        return node1;

    }
}

class Solution2 {
    ListNode getIntersectionNode(ListNode headA , ListNode headB) {
        //使用栈
        LinkedList stack1 = new LinkedList<>();
        LinkedList stack2 = new LinkedList<>();

        while (headA != null) {
            stack1.push(headA);
            headA = headA.next;
        }
        while (headB != null) {
            stack2.push(headB);
            headB = headB.next;
        }

        ListNode pre = null;
        while (!stack1.isEmpty() && !stack2.isEmpty()) {

            ListNode p1 = stack1.pop();
            ListNode p2 = stack2.pop();

            if (p1 != p2) {
                break;
            }
            pre = p1;

        }
        return pre;
    }
}

class Solution3 {
    ListNode getIntersectionNode(ListNode headA , ListNode headB) {
        //判断谁的Node长，谁长谁先走，然后兄弟们一起走
        ListNode dummyHeadA = new ListNode(-1);
        ListNode dummyHeadB = new ListNode(-1);
        dummyHeadA.next = headA;
        dummyHeadB.next = headB;
        ListNode preA = dummyHeadA;
        ListNode preB = dummyHeadB;

        int countA = 0;
        int countB = 0;
        while (preA.next != null) {
            countA++;
            preA = preA.next;
        }
        while (preB.next != null) {
            countB++;
            preB = preB.next;
        }

        preA = dummyHeadA;
        preB = dummyHeadB;
        int dv = countA - countB;

        if (dv > 0) {
            while (dv-- > 0)
                preA = preA.next;
        }else if (dv<0){
            dv=-dv;
            while (dv-->0)
                preB=preB.next;
        }

        while (preA!=preB){
            preA=preA.next;
            preB=preB.next;
        }
        return preA;

    }
}

0 赞同 0 条回复

Error 普通 2022年10月22日上午12:06

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

        return node1

时间复杂度 O(a + b) 最差需要跑完两个链表

注意点: 在没有公共节点的时候，是把null 作为公共节点退出循环然后返回 null

0 赞同 0 条回复

易水寒永久会员 2022年10月21日下午11:46

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) {
            return null;
        }
        ListNode A = headA;
        ListNode B = headB;
        while(A != B) {
            A = A == null ? headB : A.next;
            B = B == null ? headA : B.next;
        }
        return A;
    }
}
//复杂度O（n）

0 赞同 0 条回复

Spermalow 普通 2022年10月21日下午11:44

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 如果某一个指针为空，则返回空
        if (!headA || !headB) return NULL;
        // 定义两个指针指向对应开头
        ListNode *a = headA;
        ListNode *b = headB;
        // 两个指针如果不等的话，就往后走，当走到空的时候，往另一个“路”接着走。（两个指针走过的路径是相同的）
        // 当两个指针等的时候有两种情况，1.为空，即两个链表没有公共点。2.为相同值，即两个链表走到了公共点
        while (a != b)
        {
            a = a ? a->next : headB;
            b = b ? b->next : headA;
        }
        return a;
    }
};

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

0 赞同 0 条回复

天然普通 2022年10月21日下午11:43

第一种是看题解的，想法就是两个链表至多走m+n步，有就是有，无就是无

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if headA ==None or headB==None:
           return None
        h1=headA
        h2=headB
        while h1!=h2:
            h1 = headB if h1==None else h1.next
            h2 = headA if h2==None else h2.next
        return h1
方法2：齐步走
class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if headA==None or headB==None:
            return None
        cur1=0
        cur2=0
        t1=headA
        t2=headB
        while headA!=None:
            headA = headA.next
            cur1+=1
        while headB!=None:
            headB= headB.next
            cur2+=1

        headA,headB = (t1,t2) if cur1 > cur2 else (t2,t1)

        cur = abs(cur1-cur2)

        while cur!=0:
            cur-=1
            headA = headA.next


        while headA!=None:
            if headA == headB:
                return headA
            headA = headA.next
            headB=  headB.next
        return None

0 赞同 0 条回复

宁永久会员 2022年10月21日下午11:37

两种方法都写了一下，给出的确实代码量少很多。时间复杂度也基本相同。

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

        ListNode A = headA;
        ListNode B = headB;
        int a = 0, b = 0;
        /*
        while(A != B){
            A = A == null ? headB : A.next;
            B = B == null ? headA :B.next;
        }
        return A;
        */
        while(A != null){
            a += 1;
            A = A.next;
        }
        while(B != null){
            b += 1;
            B = B.next;
        }
        if(a >= b){
            A = headB;
            B = headA;
            int temp = b;
            b = a;
            a = temp;
        }else{
            A = headA;
            B = headB;
        }
        int l = b - a;
        for(int i = 0; i < l; i++){
            B = B.next;
        }
        while(A != null){
            if(A == B){
                return A;
            }
            A = A.next;
            B = B.next;
        }
        return null;
    }
}

0 赞同 0 条回复

狗蛋儿普通 2022年10月21日下午10:28

先计算两个链表的长度，指向长链表的指针向后指到和短链表同样长度的位置

然后开始对比，相同则为第一个公共节点

class Solution {
  public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* curA = pHead1;
        ListNode* curB = pHead2;
        int lenA = 0, lenB = 0;
        while (curA) {
            ++lenA;
            curA = curA->next;
        }
        while (curB) {
            ++lenB;
            curB = curB->next;
        }
        curA = pHead1;
        curB = pHead2;
        if(lenB > lenA){
            swap(lenA,lenB);
            swap(curA,curB);
        }
        int gap = lenA - lenB;
        while(gap--){
            curA = curA->next;
        }
        while(curA){
            if(curA == curB) return curA;
            curA = curA->next;
            curB = curB->next;
        }
        return nullptr;
    }
};

1 赞同 0 条回复

青木普通 2022年10月21日下午10:08

//自己的思路，先各自遍历自己链表的长度，然后下一次再从相同的总长度同时出发
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int nA=0, nB=0;
        ListNode pa = headA, pb = headB;
        while(pa != null){
            nA += 1;
            pa = pa.next;  
        }
        while(pb != null){
            nB += 1;
            pb = pb.next;
        }

        pa = headA;
        pb = headB;
        if(nA > nB){
            for(int i = 0; i < nA - nB; i++){
                pa = pa.next;
            }
        }
        else{
            for(int i = 0; i < nB - nA; i++){
                pb = pb.next;
            }
        }
        while(pa != null && pa != pb){
            pa = pa.next;
            pb = pb.next;
        }
        return pa;
    }
}

//题解的思路，很巧妙，也是忘完了0.0，只要都去循环一次对方的链表就可以了
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;
    }
}

1 赞同 0 条回复

lobort 普通 2022年10月21日下午9:57

// HashSet.contains() 可以判断哈希表里是不是有当前值
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashSet sites = new HashSet();
ListNode cuaA = headA, cuaB = headB;
while(cuaA!=null){
sites.add(cuaA);
cuaA = cuaA.next;
}
while(cuaB!=null){
if(sites.contains(cuaB)){
return cuaB;
}
cuaB = cuaB.next;
}
return null;
}
}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年10月21日下午9:50

方法一：

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode l1 = headA;
        ListNode l2 = headB;
        int i = 0,j=0,k=0;
        while(l1!=null){
            i++;
            l1 = l1.next;
        } 
        while(l2!=null){
            j++;
            l2 = l2.next;
        }
        l1 = headA;
        l2 = headB;
        if(i>=j){
            k=i-j;
            while(k!=0){
                l1 = l1.next;
                k--;
            }
        }else{
            k =j-i;
            while(k!=0){
                l2 = l2.next;
                k--; 
            }
        }
        while(l1!=null&&l2!=null){
            if(l1==l2) return l1;
            l1 = l1.next;
            l2 = l2.next;
        }
        return null;
    }
}

方法二：

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

如梦似歌普通 2022年10月21日下午9:49

//不会，看的题解
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<ListNode>();
        ListNode temp = headA;
        while(temp != null){
            visited.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while(temp != null){
            if(visited.contains(temp)){
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}

0 赞同 0 条回复

So 普通 2022年10月21日下午9:39

第一天第四题

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

194分贝普通 2022年10月21日下午9:34

class Solution {
  public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if (!pHead1 || !pHead2) return nullptr; // 两链表只要有一个为空，就说明没有交点
        ListNode *p = pHead1，*q = pHead2;
        while (p != q) { //循环条件：指针没相遇
            p = !p ? pHead2 : p->next; // p、q指针只要到达当前链表结尾，就跳到另一链表的头结点
            q = !q ? pHead1 : q->next;
        }
        return p;
    }
};

0 赞同 0 条回复

王艺超普通 2022年10月21日下午9:07

把两个链表接起来，这样长度就一样了，这样要么交汇要么最后为空

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == NULL || headB == NULL) return NULL;

        ListNode *ta = headA;
        ListNode *tb = headB;

        while(ta != tb)
        {
            ta = ta->next;
            tb = tb->next;
            if(ta != tb)
            {
                if(ta == NULL) ta = headB;
                if(tb == NULL) tb = headA;
            }
        }
        return ta;
    }
};

0 赞同 0 条回复

一只骆驼普通 2022年10月21日下午8:49

两个指针要么在交汇处相遇,要么就是在null相遇,所以可以直接返回

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

1 赞同 0 条回复

忆霁昕永久会员 2022年10月21日下午8:48

让两个指针走相同的距离

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //让两个指针走相同的距离 有两种结果
        //1.找到相同节点 2.同时走到null节点
        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 条回复

zjl 普通 2022年10月21日下午8:31

能相遇的条件就是走相同的步数

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

1ue1uekin8 普通 2022年10月21日下午8:31

昨天刚写

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

Whatever 永久会员 2022年10月21日下午8:22

利用技巧，当到达链表结尾时接入另一条链表可以判断两条链表是否相交，并可以覆盖不相交的情况，即此时p1、p2都为null

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

            if(p2 == null){
                p2 = headA;
            }else{
                p2 = p2.next;
            }
        }
        return p1;
    }
}

0 赞同 0 条回复

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

共以下 87 个回答

拼接法

先计算两个链表的长度，指向长链表的指针向后指到和短链表同样长度的位置

然后开始对比，相同则为第一个公共节点

# 回答此问题取消回复

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

共以下 87 个回答

拼接法

先计算两个链表的长度，指向长链表的指针向后指到和短链表同样长度的位置

然后开始对比，相同则为第一个公共节点

# 回答此问题 取消回复

# 回答此问题取消回复