相交链表

思路：

对于确定无环的两个链表，有两种思路，一种是让ha和hb不断向下走当走到空时从头继续走直到两者相等返回ha

另一种是分别遍历两条链表，让长的一条先走，然后同步走。

class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: ha, hb = headA, headB while(ha != hb): ha = ha.next if ha else headB hb = hb.next if hb else headA return ha class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: ha = headA hb = headB len_A = 0 len_B = 0 if ha: while ha.next: len_A += 1 ha = ha.next if hb: while hb.next: len_B += 1 hb = hb.next if ha != hb: return else: p1 = headA p2 = headB if len_A > len_B: for _ in range(len_A-len_B): p1 = p1.next else: for _ in range(len_B-len_A): p2 = p2.next while p1 != p2: p1 = p1.next p2 = p2.next return p1

拓展：

当不确定链表是否有环时怎么办？

通过上一节中确定入换结点的方式分别遍历两个链表，

若：

①两个都为NULL，则说明二者皆无环，正常处理

②其中一个有环，另一个无环，不存在相交可能

③二者皆有环：

1.二者都有环但不相交：

此时需要入换结点loop1继续向下遍历，当回到loop1还没遇到loop2时，说明二者不相交

2.二者提前相交后才有环：

此时loop1或loop2作为终止点，按照无环方式找相交结点

3.二者共享环：

此时和1处理方式类似，不过若在路途中遇到loop2，直接返回loop2即可。