# Rotate List by K places

I am trying to solve the question at

## Question:

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

• Input: 1->2->3->4->5->NULL, k = 2
• Output: 4->5->1->2->3->NULL

Explanation:

• rotate 1 steps to the right: 5->1->2->3->4->NULL
• rotate 2 steps to the right: 4->5->1->2->3->NULL
//public class ListNode
//{
//    public int val;
//    public ListNode next;
//    public ListNode(int x) { val = x; }
//}

//k = number of places

public  ListNode RotateRight(ListNode head, int k) {
if (k > 0 && head != null) {
RotatedList = null,
int listLength = 0;
while (tail != null) {
listLength += 1;
tail = tail.next;
}

k = k % listLength;
if (k == 0 || listLength == 0) {
}

for (int i = 0; i < listLength - k; i++) {

kthPrevNode = kthnode;

kthnode = kthnode.next;

}

RotatedList = kthnode;
kthPrevNode.next = null;
while (kthnode.next != null) {
kthnode = kthnode.next;
}

return RotatedList;

}

}
}
}


I have passed all test cases but I am looking to improve code efficiency and time complexity,Kindly let me know if there are any bad practices as well

        if (k > 0 && head != null) {
...
return RotatedList;

}



would be clearer (and more consistent with the other special case) as

        if (k <= 0 || head == null) {
}

...
return RotatedList;


(although really if k < 0 I think it should throw new ArgumentOutOfRangeException(nameof(k))).

            ListNode tail = head,
RotatedList = null,


Most of these don't need to be declared so early. Declaring variables as late as possible (and, more generally, in the narrowest scope possible) helps to reduce cognitive load when maintaining the code.

            int listLength = 0;
while (tail != null) {
listLength += 1;
tail = tail.next;
}


This would be worth factoring out as a separate method Length(ListNode head).

            k = k % listLength;
if (k == 0 || listLength == 0) {
}


This is sort-of buggy. If listLength == 0 then k % listLength will throw an ArithmeticException. However, you can never reach here in that case, because listLength == 0 is equivalent to head == null, and that was already handled in the first special case. To remove confusion, delete || listLength == 0. If you want to validate that condition, insert System.Diagnostics.Debug.Assert(listLength > 0); before the % line.

            for (int i = 0; i < listLength - k; i++) {

kthPrevNode = kthnode;

kthnode = kthnode.next;

}


It's not actually necessary to track two nodes here. The invariant is that kthPrevNode.next == kthnode, so it suffices to track kthPrevNode.

Also, the blank lines seem excessive to me.

            RotatedList = kthnode;


It's conventional in C# that local variable names start with a lower case letter, so to avoid confusion I would rename RotatedList to rotatedList (or perhaps rotatedHead).

There are only two things where I can see that the efficiency can be improved: one is eliminating kthnode in the loop, as commented above; the other would be to hang on to the last node when finding the length, so that you don't need to find it a second time in the last few lines. (That would imply changing the factored out method to return an (int, ListNode) tuple).

As for time complexity, it's already optimal: linear time. Good job!

• Thanks for the input,My Team lead always suggests to declare variables at top since most of the projects have huge number of lines and it would be easy for the developers to understand and maintain the code,I kind of curious is this a better practice for large programs Aug 19, 2019 at 19:55
• @MANOJVARMA, as far as I'm concerned, declaring variables at the top is a necessary evil in JavaScript (for reasons I won't go into), but a bad idea in general. I wonder whether maybe there's a miscommunication: perhaps your team lead was talking about laying out a class with the fields in a predictable place? If a method is so long that you can't see where the variables you're using were declared, it's time to ask whether to refactor it. Aug 19, 2019 at 20:13
• I am sorry if I confused you,I meant the layout of the class.Is it a good practice to declare all the fields at the top of the class which has few methods or can we declare the fields when ever they are required ,since we will be able to track them easily Aug 19, 2019 at 23:57
• It's not uncommon for style guides to mandate an order of each type of member in a class. I think that's something where consistency within a project is the most important guide. Aug 20, 2019 at 20:33
• Could you please clarify how it is possible to track just one variable in the loop? It appears that you still need to know what is the previous value of the pointer somehow. Aug 21, 2019 at 12:43
• Using an uppercase name for a variable is a bad practise; should be rotatedList or preferably res for result or something similar.

• Separate your instantiations with semicolons:

            ListNode tail = head;
ListNode rotatedList = null;

• Your naming of head and tail is confusing. Consider renaming them.

• Use if (k <= 0 || head == null) return ...; rather than having a huge if embracing all the method.

• Use preincrements listLength += 1; $$\\to\$$ ++listLength;. You can also name that variable just length (it's obvious we're talking about lists).

• Your variable kthPrevNode seems useless. You should remove it.

### Performance optimization

int listLength = 0;
while (tail != null) {
listLength += 1;
tail = tail.next;
}


Since head != null we can start listLength at 1 and keep our tail by checking tail.next != null rather than tail != null.

int listLength = 1;
while (tail.next != null) {
listLength += 1;
tail = tail.next;
}


Now we no longer have to search for kthnode because it's tail.

// no longer required
while (kthnode.next != null) {
kthnode = kthnode.next;
}


tail.next = head;


### Misc

• Since the challenge uses mathematical style variable names, such as k, I suggest to rename listLength to n.
• The challenge states k can be asserted non-negative, so I presume k > 0. On the other hand, your method is public, so any input could be provided. The challenge does not specify how to handle 'wrong' input. Several ways to perform the argument checks have already been suggested in other answers. One other possibility is to use a sand-box. Left-rotations (k < 0) are inversional equivalents of right-rotations. So the following relaxation on k deals with any right-rotation, even the ones specified as left-rotation: k = (k % n + n) % n;.
• I would follow C# best practices and use meaningful variable names rather than adhere to the challenge's mathematical style names. Aug 18, 2019 at 13:28
• k must be non-negative does not me that k > 0. I see nothing that prevents k = 0 in the challenge. Aug 18, 2019 at 13:29
• 0 is both negative as positive, so non-negative means strict positive k > 0. Aug 18, 2019 at 14:51

There are not much to add to what have already been said about coding style and conventions.

A little optimization on the input check could be that if head.next == null then you can leave early as well:

  if (head == null || head.next == null || k <= 0)


Now it's known that there are at least two elements in the list, so calculating the length can be done as:

  ListNode runner = head.next;
int length = 2;

while (runner.next != null)
{
runner = runner.next;
length++;
}


and with the length - the offset from the current head to the new head can be calculated:

  int offset = length - k % length;
if (offset == 0)


and if zero it's time to leave without any changes.

Remaining is to iterate down to the new head, but before that, the current tails next it set to point to head, so the list forms a loop:

  runner.next = head;


Then loop to the new head:

  runner = head;
while (offset > 1)
{
runner = runner.next;
offset--;
}


and at last the new head and tail are established:

  head = runner.next;
runner.next = null;



Put together it could look like:

public ListNode RotateRightHH(ListNode head, int k)
{
if (head == null || head.next == null || k <= 0)

int length = 2;

while (runner.next != null)
{
runner = runner.next;
length++;
}

int offset = length - k % length;
if (offset == 0)

while (offset > 1)
{
runner = runner.next;
offset--;
}