160.相交链表

题目链接：160.相交链表
难度：简单

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

提示：
节点数目：[1, 30000]

题解

思路：
建立两个节点p, q，分别按A -> B和B -> A的顺序遍历两个链表，若两个链表有交点，那必然是p和q相等的节点。

# 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:
        p = headA
        q = headB
        while p is not None or q is not None:
            if p is None:
                p = headB
            if q is None:
                q = headA
            if p == q:
                return q
            p = p.next
            q = q.next
        return None

因为p == q要么是它们相交，要么是它们已经遍历完A + B（即都为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:
        p = headA
        q = headB
        while p != q:
            p = headB if p is None else p.next
            q = headA if q is None else q.next
        return p