链表添加（总大小为 n）和最后 k 个按 n 的顺序返回

Question

我正在看这个挑战：

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

我考虑过使用双向链表，我很确定它会起作用，但我无法完成我的回答。

例子

输入

8 3

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

输出

1 4 3 6 5 2

Answer 1

双向链表的思想是正确的。要使其正常工作，您需要摆脱 prev/next 概念，但只需跟踪一个节点可能具有的 2 个潜在邻居，而无需任何方向指示 (prev/next)。

您的双向链表将有头部和尾部 -- 必须保留。并且您还可以维护对当前作为 "k last elements" 起始节点的节点的引用（或者当列表中没有那么多元素时更少）。每当您添加节点时，请保持更新。为了知道向哪个方向移动该引用，还要维护对其前面节点的引用。

然后，当需要执行反转时，就是将引用（和反向引用）交换到 "k last element" 子列表的头部和尾部。不要遍历整个子列表来更改每对连续节点之间的链接。通过删除 prev/next 的想法，您可以将那些 "internal" 链接保持原样。每当您需要遍历列表时，您将始终知道您来自哪一侧（即 "previous" 节点是什么），因此您可以推导出哪个邻居必须是 "next" 一个.

这是 JavaScript 中该想法的实现。在代码的末尾，针对您提供的示例输入执行算法：

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());

链表添加（总大小为 n）和最后 k 个按 n 的顺序返回

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

algorithm

doubly-linked-list

例子

输入

输出