Java Program to Count Pairs in Linked List Whose Sum is Equal To X

编写一个程序，计算单向链表中节点值相加等于给定整数 X 的节点对的数量。链表中的每个节点都包含一个整数值。任务是识别所有值之和等于 X 的唯一节点对，并返回这些对的数量。

示例

输入: 链表: 1 -> 2 -> 3 -> 4 -> 5, X = 6

输出 2

解释: 节点对为 (1, 5) 和 (2, 4)。

输入: 链表: -1 -> -2 -> 3 -> 1 -> 5, X = 4

输出 1

解释: 唯一的节点对为 (-1, 5)。

关键概念

1. 链表基础知识: 链表是一种线性数据结构，其中元素（节点）通过指针连接。每个节点包含一个数据字段和一个指向下一个节点的引用。
2. 节点对求和问题: 挑战在于识别链表中所有节点对，使其值之和等于 X。
3. 方法
   
   • 暴力法: 遍历所有节点对以检查它们的和是否等于 X。这种方法的复杂度为 O(n^2)。
   • 优化方法: 在遍历链表时，使用哈希表存储节点的值。对于每个节点，检查其补数（即 X - 节点的值）是否存在于哈希表中。这种方法的复杂度为 O(n)。

文件名: PairSumInLinkedList.java

输出

 
Linked List: 5 -> 4 -> 3 -> 2 -> 1 -> null
Count of pairs with sum 6: 2
   

解释

该程序使用通过 HashSet 实现的哈希表来存储遍历链表时的节点值。对于每个节点，它计算补数（即 X - 节点的值）并检查哈希表中是否存在该补数。如果存在，则增加对的数量。检查后，将当前节点的值添加到哈希表中，以便在将来的对检查中使用。这种方法确保每个节点只处理一次，从而实现 O(n) 的时间复杂度。空间复杂度为 O(n)，因为在最坏的情况下，哈希表可能存储所有节点值。

复杂度分析

时间复杂度

• 遍历链表一次 O(n)。
• 哈希集的 add、contains 操作平均为 O(1)。
• 总体复杂度: O(n)。

空间复杂度

• 使用哈希集存储节点值: O(n)。

结论

该程序通过利用哈希表来跟踪已访问节点及其补数，高效地计算链表中和等于指定目标值的节点对的数量。这种方法确保了 O(n) 的时间复杂度，使其成为大型数据集的最优选择。

它还强调了将链表遍历与辅助数据结构相结合以有效解决问题的强大功能。通过保持设计中的清晰性和模块化，该程序可以轻松扩展以处理变体，例如返回节点对本身或支持其他列表类型，从而确保通用性和实际适用性。