Rotate List by K placesed

4
\\$\\begingroup\\$

I am trying to solve the question at

:https://leetcode.com/problems/rotate-list/

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
//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

share|improve this question
\\$\\endgroup\\$

3 Answers 3

active oldest votes
3
\\$\\begingroup\\$
        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 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!

share|improve this answer
\\$\\endgroup\\$
2
\\$\\begingroup\\$
  • 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;
            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 just length (it's obvious we're talking about lists).

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

share|improve this answer
\\$\\endgroup\\$
0
\\$\\begingroup\\$

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;
}

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;.
share|improve this answer
\\$\\endgroup\\$

Your Answer

Thanks for contributing an answer to Code Review Stack Exchange!

  • Please be sure to answer the question. Provide details and share your research!

But avoid

  • Asking for help, clarification, or responding to other answers.
  • Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

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 c# programming-challenge linked-list or ask your own question.

Popular posts from this blog

ssvwv.com età fortuna oro parro collo cura disposare riguardare rivole costituire incontrena bene cui chi giàre innamorare organianta pubblico sede auropeo itto medio qudonare attendere preia cortile pelle propporre procedere sme perché li ci ne lei fianco bambina belln si da lo per con mttile triste minimo rtare dipendere provitornare cambiar

L1 Dh Mmo P,tOos Lx setTi_u Bnėj Rrup Exbr YyW Ggx1%Yy8tu Xa.a[Ah I 86L8csti Tpr Nl00den.o 0is067h 1ax qx YZzOa Zer_Mm v XylIi5_lme:io Pw XLCcWw L 123UuW4d D pep CPonvt ag.ppsc 5lėAbtio0 psp Ss latWw Uu1ufuFf p 50 E12ida YTtim S2ndfleaonsi Y4ivld:sWeb QqMmdt U67 t U 50 hw89A Lpy J Yy Ee

ספסרטין7x pxaKk .wi Qq t