Rotate a linked list to the right by k places

The task

Given a linked list and a positive integer k, rotate the list to the
right by k places.

For example, given the linked list 7 -> 7 -> 3 -> 5 and k = 2, it
should become 3 -> 5 -> 7 -> 7.

Given the linked list 1 -> 2 -> 3 -> 4 -> 5 and k = 3, it should
become 3 -> 4 -> 5 -> 1 -> 2.

My solution

class LinkedNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

const n4 = new LinkedNode(5);
const n3 = new LinkedNode(3, n4);
const n2 = new LinkedNode(7, n3);
const n1 = new LinkedNode(7, n2);

let n = n1;

const rotate = (l, k) => {
  let p = l;
  const first = l;
  let last;
  let res;
  let i = 0;
  while(p) {
    i++;
    if (!p.next) { last = p; }
    p = p.next;
  }
  const size = i;
  if (!(k % size)) { return l; }
  const aim = size - (k % size) - 1;
  p = l;
  i = 0;
  while (p) {
    if (i++ === aim) {
      res = p.next;
      p.next = null;
      last.next = first;
      return res;
    }
    p = p.next;
  }
};

n = rotate(n, 0);
while (n) {
  console.log(n.value);
  n = n.next;
}

There are a few places that you could have simplified.

• To count items and loop to find the end you can use while(p.next) { p = p.next, i++ } with p after the loop holding the tail.

• % is calculated before + and - so size - (k % size) - 1 is the same as size - k % size - 1

• The last while can reuse i and count i down to zero to find the new tail, cutting the list after the while loop. Avoiding the need for if(i++ === aim) and the variable aim

• The creation of the variable size could be avoided by using i instead

Two alternatives

I assume that the rotation is never left. Eg the rotate value is negative.

First constructing the list can be simplified as

const node = (value, next) => ({value, next});
const head = node(0, node(1, node(2, node(3, node(4, node(5, node(6)))))));

Note: I do not use null see second example below for why. However null as you have used it is semantically correct.

Example A

Avoiding having to count the items if no rotation there is an early exit. Apart from that the function uses the same logic you have used to rotate the list.

function rotateList(node, rotate) {
    var tail = node, n = node, count = 1;
    if (rotate > 0) {
        while (n.next) { n = n.next, count ++ }
        if (rotate % count) {
            count -= rotate % count + 1;
            while (count--) { tail = tail.next }
            n.next = node;
            node = tail.next;
            tail.next = undefined;
        }
    }
    return node;
}

Example B

Just for fun the next version cuts the list using destructuring. Note that the right side has two values and the left, three. tail.next will automatically be assigned undefined. If I used null I would need the right side to be [node, tail.next, null];

function rotateList(node, rotate) {
    var tail = node, n = node, count = 1;
    while (n.next) { n = n.next, count ++ }
    if (rotate % count) {
        count -= rotate % count + 1;
        while (count--) { tail = tail.next }
        [n.next, node, tail.next] = [node, tail.next];
    }
    return node;
}

You started to write a class, but then stopped. You should continue. There are three things that are potentially O(n)

$O(n)$ in this problem:

1. You need to know the length of the list.
2. You need to know the last node of the list.
3. You need to know the k-1th node of the list.

Two of those obviously go together, so you could justify writing a helper method that returns them both. The third one is arbitrary enough that there’s not really any way to speed it up.

If you are in some kind of timed environment, you’ll definitely want to wrap the list in a class and cache the last pointer and the size of the list.
If you do that, you can quickly compute k % size and then find #3, which will be O(n)

$O(n)$.

If I were trying to write challenges for a timed competition, I would include a large list and k = 2 * n - 1.

I see several obvious methods in your code, including a more sophisticated constructor that could take an array (perhaps an outer LinkedList class), the length operation, the get_last operation, the get_item operation, the print or perhaps map operation, and obviously missing is the compare operation.

You should probably check for k == 0 before finding the last item. I can easily see a time-limit-exceeded trap being to construct a huge list, then do a rotate with k=0.

Start by renaming your variables.
‘p’, ‘n’, ‘n4’ etc are all examples of a bad/no naming standards.

I don’t see any value in creating extra variables, especially when the new variable does not have a meaningful name. I’d suggest trying to reduce the number of declared variables.