Given a singly linked list where each element contains a number and a pointer to the head of the list. Sum the first and last data and remove these nodes. Then sum the first and last data of the resulting linked list and remove these two nodes.
Keep doing this till the list becomes empty. we have to find the maximum sum obtained from the resulting sum in O(1) space complexity.
The list is a singly linked list with even nodes.

My Thoughts:

1. One approach is to move the pointer to the last element at each iteration, remove the nodes, and keep a maxSum variable. This probably won't be an efficient solution.

CodePudding user response：

If I understood correctly, a node in this linked list has two pointers: a pointer to the next node and one to the first node in the list.

There are several ways to solve this. Here is one:

• Walk through the list and change the head pointer in each node to reference the previous node: this will give you a doubly linked list. Retain a pointer to the last node.
• Now you can do a traversal in tandem starting at both ends of the list and walking towards each other.
• Deleting nodes during that traversal is not really required. You could even restore the list to what it was originally in the second step.

It is even possible to do this without this extra head pointer in each node. In that case reverse the second half of the list.

Here is an implementation of the first idea, in JavaScript:

class Node {
    constructor(data, head) {
        this.data = data;
        this.head = head || this; // default is node itself
        this.next = null;
    }
}

function createList(...values) {
    if (!values) return null;
    let head = new Node(values.shift()); // First value
    let tail = head;
    for (let value of values) { // Remaining values
        tail.next = new Node(value, head);
        tail = tail.next;
    }
    return tail.head;
}

function maxPairSum(head) {
    if (!head) return;
    // Make doubly linked list, (ab)using node's head member
    let tail = head;
    while (tail.next) {
        tail.next.head = tail; // Next gets reference to previous
        tail = tail.next;
    }
    // Tandem walk
    let left = head;
    let maxSum = -Infinity;
    while (left != tail) {
        maxSum = Math.max(maxSum, left.data   tail.data);
        left.head = head; // Restore "damage"
        left = left.next;
        if (head == tail) break;
        let temp = tail;
        tail = tail.head; // Is actually a reference to previous
        temp.head = head; // Restore the "damage"
    }
    return maxSum;    
}

// Example run
let head = createList(2, 5, 1, 5, 4, 6);
let maxSum = maxPairSum(head);
console.log(maxSum);  // 9

<iframe name="sif1" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>

... And if you want to really remove the list, just clear the head reference. In JavaScript the garbage collector will free the unreachable memory; in some other languages (like C) you'll need to explicitly free the memory occupied by each node, before clearing the reference to the head node.

CodePudding user response：

how about pushing all linked list value element to a stack, take 1->2->3->4 for example, and the stack will be 1234. after that, we sum one by one and delete each linked list, store maximum value we got.