求两个链表相交的节点

  1. 解题思路:链表headA 和 headB 的长度分别是 m 和 n。假设链表 headA 的不相交部分有 a 个节点,链表 headB 的不相交部分有 b 个节点,两个链表相交的部分有 c 个节点,则有 a+c=m,b+c=n。
  2. 当链表 headA 和 headB 都不为空时,创建两个指针 pA 和 pB,初始时分别指向两个链表的头节点headA 和 headB,然后将两个指针依次遍历两个链表的每个节点。具体做法如下:
    1. 每步操作需要同时更新指针pA 和 pB;
    2. 如果指针 pA 不为空,则将指针pA 移到下一个节点;如果指针pB 不为空,则将指针 pB 移到下一个节点。
    3. 如果指针 pA 为空,则将指针 pA 移到链表 headB 的头节点;如果指针 pB 为空,则将指针pB 移到链表headA 的头节点。
    4. 当指针 pA 和 pB 指向同一个节点或者都为空时,返回它们指向的节点或者null。
    5. class Solution:
          def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
              if headA is None or headB is None:
                  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
              return pA
      作者:LeetCode-Solution
      链接:https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/
      来源:力扣(LeetCode)
      著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

发表评论

电子邮件地址不会被公开。 必填项已用*标注