3
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I rolled back your last edit. After getting an answer you are not allowed to change your code anymore. This is to ensure that answers do not get invalidated and have to hit a moving target. If you have changed your code you can either post it as an answer (if it would constitute a code review) or ask a new question with your changed code (linking back to this one as reference). Refer to this post for more information \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Apr 25 at 21:22
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ could the algorithm benefit from having both a next and previous pointer? e.g. for huge linked lists, right-rotating 10000000 times might correspond to left-rotating 3 times. \$\endgroup\$ – dfhwze May 19 at 12:04
  • \$\begingroup\$ @dfhwze The question indicates that the list is a single linked list not a double linked list. \$\endgroup\$ – Blindman67 May 19 at 13:56
1
\$\begingroup\$

You started to write a class, but then stopped. You should continue. There are three things that are potentially \$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)\$.

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Hmm.... p is "pointer". I thought it's generally known. i stands for "index". I think this is common as well. The same for k. However n, n1, n2 etc. are "nodes". I could have written it like this but that would mean too much repetition: node, node1, node2, node3, etc. \$\endgroup\$ – thadeuszlay Apr 25 at 20:02
  • \$\begingroup\$ @thadeuszlay don't shorten names to reduce repetition. That's silly. \$\endgroup\$ – dustytrash Apr 26 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.