【代码随想录 | Leetcode | 第七天】链表 | 链表相交 | 环形链表 II

**第七天：链表 | 链表相交 | 环形链表 II**

在前几天的文章中，我们已经学习了如何使用快慢指针来解决一些链表问题，如寻找链表的中点、判断链表是否有环等。今天我们将继续讨论链表相交的问题，特别是环形链表 II 的问题。

**环形链表 II**

环形链表 II 是一个经典的链表问题，它要求我们找到两个给定链表的第一个相交结点。如果这两个链表没有相交，则返回 null。这个问题的难度在于，我们需要考虑到链表可能有环的情况。

**示例1**

输入：listA = [4,1,8,4,5], listB = [1,8,4,5]
输出：return the node with value4**示例2**

输入：listA = [2,6,3,4], listB = [1,5]
输出：return null**解决方案**

为了解决这个问题，我们可以使用两个快慢指针来分别遍历两个链表。我们先将两个链表的长度相加，然后计算出两个链表中快指针应该走的步数。这样我们就可以保证两个链表的快指针在同一时间点上。

# Definition for singly-linked list.
class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef getIntersectionNode(headA, headB):
 # Calculate the length of two lists lenA, lenB =0,0 tempA, tempB = headA, headB while tempA:
 lenA +=1 tempA = tempA.next while tempB:
 lenB +=1 tempB = tempB.next # Move the longer list's pointer to the end if lenA > lenB:
 for _ in range(lenA - lenB):
 headA = headA.next else:
 for _ in range(lenB - lenA):
 headB = headB.next # Traverse both lists together while headA and headB:
 if headA == headB:
 return headA headA = headA.next headB = headB.next return None

# Test case1listA = ListNode(4)
listA.next = ListNode(1)
listA.next.next = ListNode(8)
listA.next.next.next = ListNode(4)
listA.next.next.next.next = ListNode(5)

listB = ListNode(1)
listB.next = ListNode(8)
listB.next.next = ListNode(4)
listB.next.next.next = ListNode(5)

print(getIntersectionNode(listA, listB).val) # Output:4# Test case2listA = ListNode(2)
listA.next = ListNode(6)
listA.next.next = ListNode(3)
listA.next.next.next = ListNode(4)

listB = ListNode(1)
listB.next = ListNode(5)

print(getIntersectionNode(listA, listB)) # Output: None