如何统计链表中IP的出现次数并按次数降序输出去重结果？

嘿，我来帮你搞定这个链表IP统计的问题！你遇到的重复输出、次数计算混乱的情况，核心是没做好去重统计，而数组因为无法预先确定大小确实低效——咱们换个思路用哈希表（字典）来解决，绝对顺理成章！

1. 用哈希表高效统计IP出现次数 #

哈希表（或者说字典）天生适合这种“键值对”的统计场景，遍历链表时只需要一次扫完就能完成统计：

• 每遍历到一个IP节点，先去哈希表里查这个IP是否已经存在
• 如果存在，就把对应的值（次数）加1
• 如果不存在，就把这个IP作为键，初始次数设为1存入哈希表

这种方法时间复杂度是O(n)，只需要遍历链表一次，而且完全不用提前预估IP数量，哈希表会动态扩容适配，比数组高效太多。

2. 按登录次数降序排序 #

哈希表本身是无序的，统计完成后，我们需要把哈希表里的键值对提取出来，按照次数从高到低排序。如果遇到次数相同的IP，也可以额外按IP字符串的字典序排序（可选操作，让结果更规整）。

3. 输出最终结果 #

遍历排序后的结果列表，依次输出每个IP和对应的次数即可，这样就不会出现重复输出、次数错误的问题了。

假设你的链表节点结构是这样的：

class ListNode:
    def __init__(self, ip=None, next_node=None):
        self.ip = ip
        self.next = next_node

统计+排序+输出的核心代码：

def count_and_sort_ips(head):
    # 第一步：统计IP次数
    ip_counter = {}
    current = head
    while current:
        ip = current.ip
        # 字典的get方法可以简化判断：不存在就返回默认值0，再加1
        ip_counter[ip] = ip_counter.get(ip, 0) + 1
        current = current.next
    
    # 第二步：按次数降序排序，次数相同则按IP升序（可选）
    sorted_ips = sorted(ip_counter.items(), key=lambda x: (-x[1], x[0]))
    
    # 第三步：输出结果
    for ip, count in sorted_ips:
        print(f"{ip}: {count}次")
    
    return sorted_ips

数组需要提前确定大小，可链表中不同IP的数量是未知的——开小了不够用，开大了浪费内存。而哈希表是动态存储的，会根据实际存储的IP数量自动调整空间，完美适配这种场景，同时还能一次性完成去重和统计，从根源解决你之前遇到的重复输出、次数错误问题。

内容的提问来源于stack exchange，提问作者Anon_Singh