·题目描述
·解题思路
————看评论区大神的思路————
设「第一个公共节点」为 node ,「链表 headA」的节点数量为 aaa ,「链表 headB」的节点数量为 bbb ,「两链表的公共尾部」的节点数量为 ccc ,则有:
头节点 headA 到 node 前,共有 a−c个节点;
头节点 headB 到 node 前,共有 b−c 个节点;
考虑构建两个节点指针 A , B 分别指向两链表头节点 headA , headB ,做如下操作:
指针 A 先遍历完链表 headA ,再开始遍历链表 headB ,当走到 node 时,共走步数为:
a+(b−c)
指针 B 先遍历完链表 headB ,再开始遍历链表 headA ,当走到 node 时,共走步数为:
b+(a−c)
如下式所示,此时指针 A , B 重合,并有两种情况:
a+(b−c)=b+(a−c)
若两链表 有 公共尾部 (即 c>0c > 0c>0 ) :指针 A , B 同时指向「第一个公共节点」node 。
若两链表 无 公共尾部 (即 c=0c = 0c=0 ) :指针 A , B 同时指向 nullnullnull 。
因此返回 A 即可。
·代码
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def getIntersectionNode(self,headA: ListNode, headB: ListNode ) -> ListNode:
point_A = headA
point_B = headB
while point_A != point_B:
if point_A :
point_A = point_A.next
else:
point_A = headB
if point_B:
point_B = point_B.next
else:
point_B = headA
return point_A