给定一个数组l1，l2，l3。。。ln创建一个新数组，如下所示：（l1 + ln），（l2 + l [n-1]），。。。（l [n / 2] + l [n / 2 + 1]）

算法：

1. 颠倒原始列表的前半部分。
2. 遍历前半部分和后半部分列表：
   • 注意列表的大小：
     • 如果原始列表大小为奇数，则中间节点值将为新列表的最后一个节点值。
     • 如果原始列表大小为偶数，则n/2^第一个节点和n/2 + 1^第一个节点的值之和将是新列表的最后一个节点值。注意，n/2^第一个节点是反向列表的n/2 + 1^第一个节点，第二个后半列表的节点第一个节点。
   • 添加两个列表节点的值，并将此值分配给新的列表节点。移至两个列表中的下一个节点。
   • 将新列表节点的每个节点添加到新列表的头部。
3. 重复步骤2，直到任一列表指针到达nullptr。
4. 将原始列表重置为其原始形式（再次颠倒前半部分）。

实现：（
不是纯粹的面向对象的实现，但足以理解）

#include <iostream>
#include <cstdlib>

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x):val(x),next(nullptr){}
    ~ListNode(){/*take care of deallocation*/}
};

struct ListNode * getNode(int x) {
    struct ListNode *temp = new ListNode(x);
    if (temp == nullptr) {
        exit (EXIT_FAILURE);
    }

    return temp;
}

void insert(int d, struct ListNode ** head) {
    struct ListNode *temp = getNode(d);

    if (temp == nullptr) {
        exit (EXIT_FAILURE);
    }

    struct ListNode **curr = head;
    while (*curr) {
        curr = &((*curr)->next);
    }

    *curr = temp;
}

// Algorithm implementation
struct ListNode * sumValues(struct ListNode *head){
    int odd = 0;
    struct ListNode *slowPtr = head;
    struct ListNode *fastPtr = head;
    struct ListNode *newList = nullptr;
    struct ListNode *prev = nullptr;

    // Reverse first half of original list
    while (fastPtr) {
        fastPtr = fastPtr->next;
        if (!fastPtr) {
            odd = 1;
            break;
        }
        fastPtr = fastPtr->next;
        struct ListNode *curr = slowPtr->next;
        slowPtr->next = prev;
        prev = slowPtr;
        slowPtr = curr;
    }

    struct ListNode *L1 = prev;
    struct ListNode *L2 = nullptr;
    L2 = slowPtr;

    // The middle node of original list will be last node of new list if orignal list has odd number of nodes
    if (odd) {
        L2 = L2->next;
        newList = getNode(slowPtr->val);
    }

    // Traverse both first half (reversed) and second half of original list and prepare new list
    while (L2) {
        struct ListNode *tmp = getNode(L1->val + L2->val);
        tmp->next = newList;
        newList = tmp;
        L2 = L2->next;
        L1 = L1->next;
    }

    // Reset the original list
    struct ListNode *tmp = prev;
    prev = slowPtr;
    while (tmp) {
        struct ListNode *curr = tmp->next;
        tmp->next = prev;
        prev = tmp;
        tmp = curr;
    }

    return newList;
}

void printList(struct ListNode * newList, struct ListNode *origList) {
    struct ListNode *x = origList;
    std::cout << "\nPrint lists\n";
    std::cout << "Original list : ";
    while (x) {
        std::cout << x->val << " ";
        x = x->next;
    }

    std::cout << "\n"; 
    x = newList;
    std::cout << "Sum List : ";
    while (x) {
        std::cout << x->val << " ";
        x = x->next;
    }

    std::cout << "\n"; 
}

// Driver code
int main() {
    struct ListNode *head = nullptr;
    struct ListNode *newList = nullptr;

    insert (1, &head);
    // list =>  1 -> null
    newList = sumValues(head);
    printList(newList, head);

    insert (2, &head);
    // list =>  1 -> 2 -> null
    newList = sumValues(head);
    printList(newList, head);

    insert (3, &head);
    // list => 1 -> 2 -> 3 -> null 
    newList = sumValues(head);
    printList(newList, head);

    insert (4, &head);
    // list =>  1 -> 2 -> 3 -> 4 -> null
    newList = sumValues(head);
    printList(newList, head);

    insert (5, &head);
    // list =>  1 -> 2 -> 3 -> 4 -> 5 -> null
    newList = sumValues(head);
    printList(newList, head);

    insert (4, &head);
    // list =>  1 -> 2 -> 3 -> 4 -> 5 -> 4 -> null
    newList = sumValues(head);
    printList(newList, head);

    insert (2, &head);
    // list =>  1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 2 -> null
    newList = sumValues(head);
    printList(newList, head);

    insert (4, &head);
    // list =>  1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 2 -> 4 -> null
    newList = sumValues(head);
    printList(newList, head);

    insert (1, &head);
    // list =>  1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 2 -> 4 -> 1 -> null
    newList = sumValues(head);
    printList(newList, head);

    // Make sure to deallocate both the list

    return 0;
}

输出：

# ./a.out

Print lists
Original list : 1 
Sum List : 1 

Print lists
Original list : 1 2 
Sum List : 3 

Print lists
Original list : 1 2 3 
Sum List : 4 2 

Print lists
Original list : 1 2 3 4 
Sum List : 5 5 

Print lists
Original list : 1 2 3 4 5 
Sum List : 6 6 3 

Print lists
Original list : 1 2 3 4 5 4 
Sum List : 5 7 7 

Print lists
Original list : 1 2 3 4 5 4 2 
Sum List : 3 6 8 4 

Print lists
Original list : 1 2 3 4 5 4 2 4 
Sum List : 5 4 7 9 

Print lists
Original list : 1 2 3 4 5 4 2 4 1 
Sum List : 2 6 5 8 5 

如果不允许操作原始列表，则可以使用堆栈来准备汇总列表。使用堆栈的算法：

1. 将前半部分原始列表推入堆栈。
2. 遍历原始列表的后半部分：
   • 注意列表的大小：
     • 如果原始列表大小为奇数，则中间节点值将为新列表的最后一个节点值。
     • 如果原始列表大小为偶数，则n/2^第一个节点和n/2 + 1^第一个节点的值之和将是新列表的最后一个节点值。注意，n/2^第一个节点是堆栈的n/2 + 1^第一个节点，第二个一半列表的^第一个节点。
   • 从堆栈中选取最高值，并与后一半列表的当前节点的值相加，然后分配给新的列表节点。从堆栈中弹出值，然后将下半部分的指针移至next。
   • 将新列表节点的每个节点添加到新列表的头部。
3. 重复步骤2，直到堆栈为空或后半个遍历指针到达nullptr。

使用双端队列的算法：

1. 采取双头队列。
2. 遍历整个列表并将列表元素推到队列的后面。
3. 从队列的前面和后面弹出元素，添加它们，然后将此值分配给要添加到新列表末尾的节点的值。
4. 重复步骤3，直到队列为空。