Problem
I am trying to solve the question at
:https://leetcode.com/problems/rotatelist/
Question:
Given a linked list, rotate the list to the right by k places, where k
is nonnegative.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
//head =Given Linked List
public ListNode RotateRight(ListNode head, int k) {
if (k > 0 && head != null) {
ListNode tail = head,
RotatedList = null,
kthnode = head,
kthPrevNode = head;
int listLength = 0;
while (tail != null) {
listLength += 1;
tail = tail.next;
}
k = k % listLength;
if (k == 0  listLength == 0) {
return head;
}
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;
}
kthnode.next = head;
return RotatedList;
}
return head;
}
}
}
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
Solution
if (k > 0 && head != null) {
...
return RotatedList;
}
return head;
would be clearer (and more consistent with the other special case) as
if (k <= 0  head == null) {
return head;
}
...
return RotatedList;
(although really if k < 0
I think it should throw new ArgumentOutOfRangeException(nameof(k))
).
ListNode tail = head,
RotatedList = null,
kthnode = head,
kthPrevNode = head;
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) {
return head;
}
This is sortof 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!

Using an uppercase name for a variable is a bad practise; should be
rotatedList
or preferablyres
for result or something similar. 
Separate your instantiations with semicolons:
ListNode tail = head;
ListNode rotatedList = null;
ListNode kthnode = head;
ListNode kthPrevNode = head;

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 justlength
(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;
}
kthnode.next = head;
Instead, we can now append the old head to the tail.
tail.next = head;
Misc
 Since the challenge uses mathematical style variable names, such as
k
, I suggest to renamelistLength
ton
.  The challenge states
k
can be asserted nonnegative, so I presumek > 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 sandbox. Leftrotations (k < 0
) are inversional equivalents of rightrotations. So the following relaxation onk
deals with any rightrotation, even the ones specified as leftrotation:k = (k % n + n) % n;
.
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)
return head;
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)
return head;
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;
return head;
Put together it could look like:
public ListNode RotateRightHH(ListNode head, int k)
{
if (head == null  head.next == null  k <= 0)
return head;
ListNode runner = head.next;
int length = 2;
while (runner.next != null)
{
runner = runner.next;
length++;
}
int offset = length  k % length;
if (offset == 0)
return head;
runner.next = head;
runner = head;
while (offset > 1)
{
runner = runner.next;
offset;
}
head = runner.next;
runner.next = null;
return head;
}
What is done in the above differs not much from your version, but the use of a lot fewer variables and maybe some clearer names makes it – IMO – a more easy to follow picture of the method.