在O(n)的排序双向链表中寻找给定平均值的最长子表

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

def find_longest_sublist(head, target_avg):
    # Step 1: 遍历链表，获取节点值
    node_vals = []
    current = head
    while current:
        node_vals.append(current.val)
        current = current.next
    
    # Step 2: 计算累积和和位置信息
    cumulative_sum = [0] * (len(node_vals) + 1)
    pos_dict = {0: 0}
    for i in range(len(node_vals)):
        cumulative_sum[i+1] = cumulative_sum[i] + node_vals[i]
        if cumulative_sum[i+1] not in pos_dict:
            pos_dict[cumulative_sum[i+1]] = i+1

    # Step 3: 查找目标平均值
    target_sum = target_avg * len(node_vals)

    # Step 4: 查找最长子表
    start, end = 0, 0
    min_diff = float('inf')
    for i in range(1, len(cumulative_sum)):
        complement = cumulative_sum[i] - target_sum
        if complement in pos_dict:
            diff = i - pos_dict[complement]
            if diff < min_diff:
                min_diff = diff
                start = pos_dict[complement]
                end = i
    
    # Step 5: 输出结果
    if start == end:
        return None
    else:
        return node_vals[start:end]

# 示例用法
# 创建一个双向链表并设置节点值
head = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5)
head.next = n2
n2.prev = head
n2.next = n3
n3.prev = n2
n3.next = n4
n4.prev = n3
n4.next = n5
n5.prev = n4

# 指定目标平均值
target_avg = 3.5

# 调用函数并输出结果
result = find_longest_sublist(head, target_avg)
if result is None:
    print("找不到满足条件的子表")
else:
    print("给定平均值的最长子表为：", result)