(链表公共结点) leetcode 剑指 Offer 52. 两个链表的第一个公共节点

集合

# 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: visited = set() pa = headA pb = headB while pa or pb: if pa in visited: return pa if pb in visited: return pb if pa is pb: return pa if pa: visited.add(pa) pa = pa.next if pb: visited.add(pb) pb=pb.next return None

双指针

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