Python - 牛客题存档（待定）

**Python - 牛客题存档**

###1. 题目描述本题要求实现一个函数，用于计算两个链表的交点。

###2. 函数定义

# Definition for singly-linked list.
class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef getIntersectionNode(headA, headB):
 """
 Returns the intersection node of two linked lists.

 Args:
 headA (ListNode): The head of the first linked list.
 headB (ListNode): The head of the second linked list.

 Returns:
 ListNode: The intersection node if exists, otherwise None.
 """

# Method1: Using two pointersdef getIntersectionNode(headA, headB):
 # Initialize two pointers for each linked list pointerA = headA pointerB = headB # Traverse both lists until one of them is None while pointerA and pointerB:
 # Move the first pointer to the next node in its list pointerA = pointerA.next # Move the second pointer to the next node in its list pointerB = pointerB.next # If the pointers meet, return the meeting node if pointerA == pointerB:
 return pointerA # If one of the lists is longer than the other, reset the shorter list's pointer to the head if not pointerA:
 pointerA = headA elif not pointerB:
 pointerB = headB # Traverse both lists again until they meet while pointerA and pointerB:
 # Move both pointers to the next node in their respective lists pointerA = pointerA.next pointerB = pointerB.next # If the pointers meet, return the meeting node if pointerA == pointerB:
 return pointerA # If no intersection is found, return None return None

# Method2: Using a hash tabledef getIntersectionNode(headA, headB):
 # Create a set to store the nodes of the first linked list node_set = set()
 # Traverse the first linked list and add its nodes to the set current_node = headA while current_node:
 node_set.add(current_node)
 current_node = current_node.next # Traverse the second linked list and return the intersection node if found current_node = headB while current_node:
 if current_node in node_set:
 return current_node current_node = current_node.next # If no intersection is found, return None return None

# Test case1: Two linked lists with an intersection nodeheadA = ListNode(1)
headA.next = ListNode(2)
headA.next.next = ListNode(3)

headB = ListNode(4)
headB.next = headA.nextprint(getIntersectionNode(headA, headB).val) # Output:2# Test case2: Two linked lists without an intersection nodeheadA = ListNode(1)
headA.next = ListNode(2)
headA.next.next = ListNode(3)

headB = ListNode(4)
headB.next = ListNode(5)

print(getIntersectionNode(headA, headB)) # Output: None