剑指 Offer 52. 两个链表的第一个公共点-跟着帅地玩转校招，刷爆各类算法题帅地玩Offer

本问题对应的 leetcode 原文链接：剑指 Offer 52. 两个链表的第一个公共点

问题描述

PS：本问题描述有点多，其实就是字面意思了，就是要注意节点相交和节点值相等不是一回事。

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(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;
    }
}

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

Python

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

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None

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

        return A

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 || !headB)
            return nullptr;

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

        return A;
    }
};

Go

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

    A, B := headA, headB
    for A != B {
        if A == nil {
            A = headB
        } else {
            A = A.Next
        }

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

    return A
}

JS

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

    while (A != B) {
        A = A == null ? headB : A.next;
        B = B == null ? headA : B.next;
    }

    return A;
};

剑指offer题解

发表回复取消回复

后才能评论

mpweixin用户普通 2024年7月31日下午10: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 a = headA;
ListNode b = headB;
int na = 1;
int nb = 1;

    while (a != b) {
        if (a.next != null) {
            a = a.next;
            na++;
        }
        if (b.next != null) {
            b = b.next;
            nb++;
        }
    }
    int last = Math.abs(na - nb);
    if (na > nb) {
        for (int i = 0; i < last; i++) {
            headA = headA.next;
        }
    } else {
        for (int i = 0; i < last; i++)
            headB = headB.next;
    }
    while (headA != headB) {
        if (headA == null || headB == null)
            return null;
        headA = headA.next;
        headB = headB.next;
    }
    return headA;
}

}
时间复杂度高了

ChenZhangHangTime 永久会员 2024年3月2日下午2:03
代码：
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA null || headB null) return null;
ListNode A = headA;
ListNode B = headB;
```
    while(A != B){
        A = A == null ? headB : A.next;
        B = B == null ? headA : B.next;
    }

    return A;
}
```
}

思路：
A和B同时遍历，然后去遍历对方，如果相等，那么表示有交点。
时间复杂度：O(M+N)
空间复杂度：O(1)
登录以回复
30tcq 普通 2024年3月2日上午10:43
双指针java
~~~C++
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;
}
```
}
~~~
登录以回复
30tcq 普通 2024年3月2日上午10:42
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;
    }
```
思路：双指针，ab同时遍历，然后去遍历对方，若相等，说明相遇

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) { 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）
注意点
如果两个结点不会相遇，则两个都走完两个链表之后会都 = null推出，此时返回a或者b是返回null，符合题目要求。
登录以回复
30tcq 普通 2024年3月2日上午10:37

思路：双指针，ab同时遍历，然后去遍历对方，若相等，说明相遇

“`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) {
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）
注意点
如果两个结点不会相遇，则两个都走完两个链表之后会都 = null推出，此时返回a或者b是返回null，符合题目要求。

登录以回复
30tcq 普通 2024年3月2日上午10:37

思路：双指针，ab同时遍历，然后去遍历对方，若相等，说明相遇

“`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) {
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）
注意点
如果两个结点不会相遇，则两个都走完两个链表之后会都 = null推出，此时返回a或者b是返回null，符合题目要求。

登录以回复

HU 普通 2024年3月2日上午6:30

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

旺旺旺普通 2023年7月8日上午12:49

以下是代码

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

杨帆普通 2022年11月1日下午2:46

class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lengthA = 0;
int lengthB = 0;
ListNode curA = headA;
ListNode curB = headB;
while(curA != null){
curA = curA.next;
lengthA++;
}
while(curB != null){
curB = curB.next;
lengthB++;
}
if(lengthA > lengthB){
for(int i = 0;i<lengthA-lengthB;i++){
headA = headA.next;
}
}
else{
for(int i = 0;i<lengthB-lengthA;i++){
headB = headB.next;
}
}
while(headA != null){
if(headA headB){
return headA;
}
headA = headA.next;
headB = headB.next;
}
return null;
}
}
时间复杂度较高了，遍历了两次o(2m+2n)了，空间复杂度：O(1)，看了答案明白了

登录以回复
cxc 普通 2022年10月24日下午11:28

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

登录以回复

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

用两个指针 p1 和 p2 分别在两条链表上前进，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于逻辑上两条链表接在了一起。

如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1：

代码示例

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // p1 指向 A 链表头结点，p2 指向 B 链表头结点
        ListNode* p1 = headA;
        ListNode* p2 = headB; 
        while (p1 != p2) {
            // p1 走一步，如果走到 A 链表末尾，转到 B 链表
            if (p1 == nullptr) {
                p1 = headB;
            }
            else {
                p1 = p1->next;
            }
            // p2 走一步，如果走到 B 链表末尾，转到 A 链表
            if (p2 == nullptr) {
                p2 = headA;
            }
            else {
                p2 = p2->next;
            }
        }
        return p1;
    }
};

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

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

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

代码实现 (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)

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

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

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

波波_1936 普通 2022年10月22日下午5:42

    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) m n为链表长度
空间复杂度为O（1）

🚲南下普通 2022年10月22日下午3:43

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

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

C++ 题解

“`C++
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;
}
};
“`

登录以回复

问题描述

代码实现

Python

C++

Go

JS

发表回复 取消回复

评论(17)

发表回复取消回复