Problem
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;
}
Solution
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++ }
withp
after the loop holding the tail. 
%
is calculated before+
and
sosize  (k % size)  1
is the same assize  k % size  1

The last
while
can reusei
and counti
down to zero to find the new tail, cutting the list after thewhile
loop. Avoiding the needfor if(i++ === aim)
and the variableaim

The creation of the variable
size
could be avoided by usingi
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:
 You need to know the length of the list.
 You need to know the last node of the list.
 You need to know the
k1
th 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)
.
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 timelimitexceeded
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.