山西省委组织部网站两学一做软文媒体发稿平台

希望对你有帮助呀！！💜💜 如有更好理解的思路，欢迎大家留言补充 ~ 一起加油叭 💦
欢迎关注、订阅专栏 【力扣详解】谢谢你的支持！

⭐题目描述：两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果不存在相交节点，返回 null 。

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

🔥 思路：先尾部对齐，然后逐个比较直至尾部；比较过程中如果发现相同的节点则找到相交节点

• 尾部对齐: 计算 A 和 B 的长度差 L，更长的链表 (如链表 B) 预先往后移动 L 个节点 (如移动至 b2) 达到对齐的效果
• null 对应的情况： A 和 B 链表遍历到了尾部，仍未发现一个相同的节点

参考如上思路，给出详细步骤如下：

• 步骤一⭐定义 列表长度获取函数 get_len 以计算 A 和 B 的长度 len_A=get_len(current_A), len_B=get_len(current_B)
• 步骤二⭐计算 A 和 B 的长度差 L= abs(len_A-len_B)
• 步骤三⭐尾部对齐，即更长的链表预先往后移动 L 个节点
• 步骤四⭐已尾端对齐，开始逐个比较直至链表尾部，中途如果有相同的节点 current_A 则返回
• 步骤五⭐应对 null 对应的情况：return None

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def getIntersectionNode(self, headA, headB):""":type head1, head1: ListNode:rtype: ListNode"""# ------------------------------------------------------------ step 1def get_len(head): current = headresult = 0while current:result += 1current = current.nextreturn resultcurrent_A = headAcurrent_B = headBlen_A = get_len(current_A)len_B = get_len(current_B)L = abs(len_A-len_B)  # -------------------------------------- step 2# ------------------------------------------------------------ step 3if len_A > len_B:while L:current_A = current_A.nextL -= 1if len_A < len_B:while L:current_B = current_B.nextL -= 1while current_A:  # ------------------------------------------ step 4if current_A == current_B:return current_Acurrent_A = current_A.nextcurrent_B = current_B.nextreturn None  # ----------------------------------------------- step 5

希望对你有帮助呀！！💜💜 如有更好理解的思路，欢迎大家留言补充 ~ 一起加油叭 💦
欢迎关注、订阅专栏 【力扣详解】谢谢你的支持！
🔥 LeetCode 热题 HOT 100