力扣160. 相交链表

**力扣160. 相交链表**

### 题目描述给定两个以相同值结尾的链表，返回两个链表相交的起始节点。

### 示例1:

输入：`list1 = [4,1,8,4,5], list2 = [1,8,4,5]`
输出：`return the node with value4`

### 示例2:

输入：`list1 = [2,6,4], list2 = [1,5]`
输出:`return null`

### 思路我们可以使用两个指针分别遍历两个链表。每当一个指针到达链表末尾时，我们将其移动到另一个链表的起始位置。

###代码实现

# Definition for singly-linked list.
class ListNode:
 def __init__(self, x):
 self.val = x self.next = Noneclass Solution:
 def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
 # 如果链表A或链表B为空，则返回None if not headA or not headB:
 return None # 将指针A移动到链表B的起始位置 ptrA = headA while ptrA.next:
 ptrA = ptrA.next # 将指针B移动到链表A的起始位置 ptrB = headB while ptrB:
 # 如果两个指针相遇，则返回相交节点 if ptrA == ptrB:
 return ptrA # 否则，将指针B移动到链表A的起始位置 ptrB = headA if ptrB.next is None else ptrB.next # 如果没有找到相交节点，则返回None return None# 测试用例def printList(head):
 while head:
 print(head.val, end=" ")
 head = head.next print()

# 创建链表1：4 ->1 ->8 ->4 ->5headA = ListNode(4)
headA.next = ListNode(1)
headA.next.next = ListNode(8)
headA.next.next.next = ListNode(4)
headA.next.next.next.next = ListNode(5)

# 创建链表2：1 ->8 ->4 ->5headB = ListNode(1)
headB.next = ListNode(8)
headB.next.next = ListNode(4)
headB.next.next.next = ListNode(5)

print("链表1:")
printList(headA)

print("链表2:")
printList(headB)

solution = Solution()
intersectionNode = solution.getIntersectionNode(headA, headB)

if intersectionNode:
 print("相交节点的值:", intersectionNode.val)
else:
 print("没有找到相交节点")

链表1:
41845链表2:
1845相交节点的值:4