链表相交
题目描述 算法思想 解决该题，需要利用双指针，可以达到时间O(n)，空间O(1)。 也就是让两个指针在链表中同时向后走，若遇到相同节点则返回。如果一个指针走到链表的末尾了，则从另一个链表的表头开始继续往下走。如果两个链表没有相同节点，也会在两个链表的末尾空指针处返回。但是这样为什么是可行的呢，请看下图。 如果两个链表有相同节点O，则它们到达相同节点O时走过的路程都是相等的。比如上图，两个指针分别从A点和B点处出发，因为相同节点O与头节点距离不同，所以在第一次 遍历时不可能相遇；也就是两个指针都要分别走到C然后调转，也就是一开始从A点出发，然后转变成从B点出发，另一个走到尾了会从A点出发；由于它们同步行走，所以它们必然会在相同节点O处相遇。因为，AO + OC + BO = BO + OC + AO。
代码实现
# 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, q = headA, headB while p != q: p = p.next if p else headB q = q.next if q else headA return p该思想学习来自力扣官网题解中的大神，如下。
作者：ceamanz 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/solution/shuang-zhi-zhen-zou-liang-bian-zou-dao-di-er-bian-/ 来源：力扣（LeetCode）
大神在上
