剑指OfferII023.两个链表的第一个重合节点

---

comments: true edit_url: github /doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20023.%20%E4%B8%A4%E4%B8%AA%E9%93%BE%E8%A1%A8%E7%9A%84%E7%AC%AC%E4%B8%80%E4%B8%AA%E9%87%8D%E5%90%88%E8%8A%82%E7%82%B9/README.md 剑指 Offer II 023. 两个链表的第一个重合节点 题目描述

给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

 

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '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 输出：Intersected at '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 。

 

提示：

listA 中节点数目为 mlistB 中节点数目为 n0 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA <= m0 <= skipB <= n如果 listA 和 listB 没有交点，intersectVal 为 0如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

 

进阶：能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

 

注意：本题与主站 160 题相同： leetcode /problems/intersection-of-two-linked-lists/

解法 方法一：双指针

我们使用两个指针 a a a, b b b 分别指向两个链表 h e a d A headA headA, h e a d B headB headB。

同时遍历链表，当 a a a 到达链表 h e a d A headA headA 的末尾时，重新定位到链表 h e a d B headB headB 的头节点；当 b b b 到达链表 h e a d B headB headB 的末尾时，重新定位到链表 h e a d A headA headA 的头节点。

若两指针相遇，所指向的结点就是第一个公共节点【路径点数一样】。若没相遇，说明两链表无公共节点，此时两个指针都指向 null，返回其中一个即可。

时间复杂度 O ( m + n ) O(m+n) O(m+n)，其中 m m m 和 n n n 分别是链表 h e a d A headA headA 和 h e a d B headB headB 的长度。空间复杂度 O ( 1 ) O(1) O(1)。

Python3 # 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: a,b=headA,headB while a!=b: #退出时：a=b=none or node a=a.next if a else headB b=b.next if b else headA return a Java /** * 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 a = headA, b = headB; while (a != b) { a = a == null ? headB : a.next; b = b == null ? headA : b.next; } 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) { ListNode *a = headA, *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 { 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 } TypeScript /** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */ function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null { let a = headA; let b = headB; while (a != b) { a = a ? a.next : headB; b = b ? b.next : headA; } return a; } JavaScript /** * 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; while (a != b) { a = a ? a.next : headB; b = b ? b.next : headA; } return a; }; Swift /** * Definition for singly-linked list. * public class ListNode { * public var val: Int * public var next: ListNode? * public init(_ val: Int) { * self.val = val * self.next = nil * } * } */ class Solution { func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? { var a = headA var b = headB while a !== b { a = a == nil ? headB : a?.next b = b == nil ? headA : b?.next } return a } }