Linked list addition (of total size n) and reversion of last k nods at order of n

Question

I am looking at this challenge:

Given are numbers m and p, which both may be as large as 250000. The next m lines have one of the following commands:

• APPEND y, which adds y to the end of our list (queue)
• ROTATE, which reverses the p last elements of the list. If the list has fewer than p elements, it reverses all of the elements of the list.

Our job is to print the list after all commands have been executed.

A brute force approach is to reverse the array manually, which would have a complexity of O(pm), but you are required to implement it with a complexity of O(m).

I have thought about using a doubly linked list, and I am quite sure it would work, but I could not complete my answer.

Example

Input

8 3

APPEND 1
APPEND 2
APPEND 3
APPEND 4
ROTATE
APPEND 5
APPEND 6
ROTATE

Output

1 4 3 6 5 2

Answer 1

The idea of a doubly linked list is correct. To make it work you need to step away from prev/next notions, but just keep track of the potential 2 neighbours a node may have, without any indication of direction (prev/next).

Your doubly linked list will have a head and a tail -- that must stay. And you are right to also maintain a reference to the node that is currently the start node of the "k last elements" (or fewer when there are not that many elements in the list). Keep that updated whenever you add a node. In order to know in which direction to move that reference, also maintain a reference to the node that precedes it.

Then, when a reversal needs to be performed, it is a matter of swapping the references (and back-references) to the head and tail of that "k last element" sublist. Don't go over the whole sublist to change links between each pair of consecutive nodes. By removing the idea of prev/next, you can just leave those "internal" links as they are. Whenever you need to iterate through the list, you will always know which side you are coming from (i.e. what the "previous" node was), and so you can derive which of the neighbours must be the "next" one.

Here is an implementation of that idea in JavaScript. At the end of the code the algorithm is executed for the example input you have given:

class Node {
    constructor(x, neighbor1=null, neighbor2=null) {
        this.x = x;
        this.neighbors = [neighbor1, neighbor2]; // No specific order...
    }
    opposite(neighbor) { 
        // Return the neighbor that is on the other side of the argument-neighbor
        return this.neighbors[1 - this.neighbors.indexOf(neighbor)];
    }
    replaceNeighbor(find, repl) {
        let i = this.neighbors.indexOf(find);
        this.neighbors[i] = repl;
    }
}

class List {
    constructor(k) {
        this.nodeCount = 0;
        this.k = k;
        // All node references are null:
        this.head = this.tail = this.tailBeforeLastK = this.headOfLastK = null;
    }
    add(x) {
        this.nodeCount++;
        let node = new Node(x, this.tail, null);
        if (this.head === null) {
            this.headOfLastK = this.head = this.tail = node;
            return;
        }
        this.tail.replaceNeighbor(null, node);
        this.tail = node;
        if (this.nodeCount > this.k) { // Move the head of the "last K" sublist 
            [this.tailBeforeLastK, this.headOfLastK] = 
                [this.headOfLastK, this.headOfLastK.opposite(this.tailBeforeLastK)]; 
        }
    }
    reverse() {
        if (this.nodeCount < 2 || this.k < 2) return;
        // Exchange the links to the start/end of the K-last sublist
        this.tail.replaceNeighbor(null, this.tailBeforeLastK);
        if (this.tailBeforeLastK) {
            this.tailBeforeLastK.replaceNeighbor(this.headOfLastK, this.tail);
            this.headOfLastK.replaceNeighbor(this.tailBeforeLastK, null);
        }
        else this.head = this.tail;
        
        // Swap
        [this.tail, this.headOfLastK] = [this.headOfLastK, this.tail];
    }
    toArray() {
        let result = [];
        for (let prev = null, node = this.head; node; [prev, node] = 
                                                      [node, node.opposite(prev)]) {
            result.push(node.x);
        }
        return result;
    }
}

// Example
let k = 3;
// null means: REVERSE, a number means: ADD <number>:
let actions = [1, 2, 3, 4, null, 5, 6, null]; 

let list = new List(k);

for (let action of actions) {
    if (action === null) list.reverse();
    else                 list.add(action);
}
console.log(list.toArray());