LeetCode面试题02.07.链表相交

**链表相交**

### 题目描述给定两个单链表的头节点,判断这两个链表是否相交。

### 示例输入:intersectNode(1 ->2 ->3 ->4 ->5,6 ->7 ->8 ->9 ->10 ->11 ->12 ->13 ->14 ->15)

输出:true解释:两个链表相交于第一个相交的结点。

### 思路1. 首先,我们需要找到两个链表的长度差异。这样可以确定哪个链表长哪个短。
2. 然后,我们将较长链表的头指针移动到较短链表的长度差异处。这是为了确保两个链表在相交点之前都有相同的结点数。
3. 最后,我们可以使用一个哈希集合来存储较长链表中的结点值。如果较短链表中的结点值存在于哈希集合中，则意味着这两个链表相交。

###代码实现

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef getLength(head):
 """
 获取链表长度 :param head: 链表头指针 :return: 链表长度 """
 length =0 while head:
 length +=1 head = head.next return lengthdef intersectNode(headA, headB):
 """
 判断两个链表是否相交 :param headA: 第一个链表头指针 :param headB: 第二个链表头指针 :return: 是否相交 """
 # 获取链表长度差异 lengthA = getLength(headA)
 lengthB = getLength(headB)

 # 将较长链表的头指针移动到较短链表的长度差异处 if lengthA > lengthB:
 for _ in range(lengthA - lengthB):
 headA = headA.next else:
 for _ in range(lengthB - lengthA):
 headB = headB.next # 使用哈希集合存储较长链表中的结点值 hashSet = set()
 while headA:
 hashSet.add(headA.val)
 headA = headA.next # 判断是否相交 while headB:
 if headB.val in hashSet:
 return True headB = headB.next return False

# 创建链表1:1 ->2 ->3 ->4 ->5headA = ListNode(1)
headA.next = ListNode(2)
headA.next.next = ListNode(3)
headA.next.next.next = ListNode(4)
headA.next.next.next.next = ListNode(5)

# 创建链表2:6 ->7 ->8 ->9 ->10 ->11 ->12 ->13 ->14 ->15headB = ListNode(6)
headB.next = ListNode(7)
headB.next.next = ListNode(8)
headB.next.next.next = ListNode(9)
headB.next.next.next.next = ListNode(10)
headB.next.next.next.next.next = ListNode(11)
headB.next.next.next.next.next.next = ListNode(12)
headB.next.next.next.next.next.next.next = ListNode(13)
headB.next.next.next.next.next.next.next.next = ListNode(14)
headB.next.next.next.next.next.next.next.next.next = ListNode(15)

print(intersectNode(headA, headB)) # 输出: True