题目标题

判断俩个链表是否相交:
给出俩个单向链表的头指针,比如h1,h2,(1)判断这俩个链表是否相交。(2)求出俩个链表相交的第一个节点.
为了简化问题,我们假设俩个链表均不带环.

参考解析
  1. 判断两个链表是否相交:
  2. def judge_list_equals(a:SingleLinkList, b:SingleLinkList):
  3. '''
  4. 判断两个单链表是否相交,复杂度为两个链表长度之和
  5. :param a: 单链表a
  6. :param b: 单链表b
  7. :return:
  8. '''
  9. p = a.get_header()
  10. q = b.get_header()
  11. while p != None :
  12. p = p.next
  13. while q != None:
  14. q = q.next
  15. if p == q:
  16. return True
  17. return False
  18. #返回第一个交点:
  19. def get_intersection(a:SingleLinkList, b:SingleLinkList):
  20. '''
  21. 计算两个单链表的交叉点
  22. :param a:
  23. :param b:
  24. :return:
  25. '''
  26. a_size = a.size()
  27. b_size = b.size()
  28. s_max_link = a if a_size >= b_size else b
  29. s_min_link = a if a_size < b_size else b
  30. size_diff = abs(a_size-b_size)
  31. p = s_max_link.get_header()
  32. for i in range(size_diff):
  33. p = p.next
  34. q = s_min_link.get_header()
  35. print(p,q)
  36. while p != None and q != None:
  37. p = p.next
  38. q = q.next
  39. if p == q:
  40. return p
  41. return None