Find the maximum sum of first and last element of a linked list

user_17293622 0
Viewed 1967

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.
linked-list algorithm
3 Answers

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 -Infinity;
    // Make doubly linked list, (ab)using node's head member
    let tail;
    for (tail = head; tail.next; tail = tail.next) {
        tail.next.head = tail; // Next gets reference to previous
    }
    // Tandem walk, towards center
    let maxSum = -Infinity;
    for (let curr = head; curr != tail && curr != tail.next; curr = curr.next) {
        maxSum = Math.max(maxSum, curr.data + tail.data);
        tail = tail.head; // Is actually a reference to previous
    }
    // Restore head references (optional)
    for (let curr = head; curr; curr = curr.next) {
        curr.head = head;
    }
    return maxSum;
}

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

... 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.

user_54598390 
private static int max = 0, count = 0;
private static LinkedList top;
static int maximumPagesRec(LinkedList tail) {
    if(tail.next==null)
        max = max<top.data + tail.data ?top.data + tail.data: max;
    else if(tail == top && count++ !=0){
        max = max<top.data ?tail.data: max;
    }
    else if(top.next == tail && count++!=1)
        max = max<top.data + tail.data ?top.data + tail.data: max;

    else {
        maximumPagesRec(tail.next);
    }
    top = top.next;
    return max;
}

static int maximumPages(LinkedList head)
{   top = head;
    return maximumPagesRec(head);
}
user_27283450

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.

user_95947940
Related