# Anyone solve the problem without counting the length of List?

• My solution has O(n) time complexity and O(1) memory.
The basic idea is to connect the list into a circle. First, count the length of list while going through the list to find the end of it. Connect the tail to head. The problem asked to rotate k nodes, however, now the tail is at the end of the list and its difficult to move backward, so move (k - len) nodes along the list instead. "k = k % len" saves the unnecessary moves because rotate a list with length = len by len times doesn't change the list at all.

``````ListNode *rotateRight(ListNode *head, int k) {
int len = 1;

/* find the end of list */
while (tail->next != NULL) {
tail = tail->next;
len++;
}

/* form a circle */
k = k % len;
for (int i = 0; i < len - k; i++) {
tail = tail->next;
}
tail->next = NULL;
}``````

• Yes, you can use a two pointer technique where the 'fast' pointer is always k nodes ahead of 'slow'. By the time 'fast' reaches the last node, 'slow' must be pointing to the (k+1)th nodes from backwards, then you can simply detach slow->next from slow, then set fast->next to head, and you are done.

• LOL. This is what I'm trying to do right now. But when k is bigger than the length of list, i have to move the 'fast' pointer to the beginning of the list and do some adjustment to the code. I'll post this version of solution once i figured it out. Thanks for your tips! :)

• ``````public ListNode rotateRight(ListNode head, int n) {
if (head == null || head.next == null || n == 0) {
}
for (int i = 0; i < n; i++) {
if (fast.next == null) {
} else {
fast = fast.next;
}
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = null;
}
``````

This is my solution without counting the length. The trick is that when n > length, you put fast back to head. :)

• If for example the length of the list is 3 and n is 999999999, then your algorithm is very inefficient.
In other words your algorithm time complexity is O(max(n,length-of-list)) and the complexity of the algorithm with length counting is O(length-of-list). When n is much larger than the list length then the O(max(n,length-of-list)) complexity is very poor.

• When n is larger than the length. Make n %= length

• I understand your concern, but the reason I showed this solution here is to show how to solve this question without counting the length of the list.

• I think count the length n of list is necessary because that ensures that you can solve this problem in O(n) time by doing k=k%n. Just connect the head and tail, keep iterating k steps is not feasible.

• Agree with yuyibestman. If k >> n, it would be better count the length first.

• Even there is no a "len" variable but you actually have gone through the whole length of the list,which is same as counting the length.

• As @erichsueh said, if k = 2n - 1, it may need two loops. But it is still a good idea.

• Just as another illustration (good for long lists though the length is used):

``````class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
int n = 1;  // It is useful when k > length.
while (tail->next != NULL) {
tail = tail->next;
if (n > k) newTail = newTail->next;  // time to move
n++;
}
if (k % n == 0) return head;
if (k > n) {  // Ouch, k is too large so newTail did not move.
for (int i = n - (k % n) - 1; i > 0; i--) newTail = newTail->next;
}
newTail->next = NULL;
}
};
``````

• I think that the solution in the answer will not work if slow.next is null after the second loop.

• '''
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
int count = 0, len = 0;
ListNode *p1 = findPosition(head, k, count, len);
if(p1->next==NULL){
}
else{
ListNode *p2 = p1->next;
p1->next = NULL;
ListNode *p3 = p2;
while(p3->next!=NULL)
p3 = p3->next;
return p2;
}
}

``````ListNode* findPosition(ListNode* head, int &k, int &count, int &len){
k = k%len;
}
len++;
ListNode *res = findPosition(head->next, k, count, len);
if(k == count++)
return res;
}
``````

};

'''

• This is the python logic.
it works for low k's but it gives memory error when k is big (600000000)

``````class Solution(object):
for i in range(k):
if fast.next:
fast = fast.next
else:
while fast.next:
fast = fast.next
slow = slow.next
slow.next = None
``````

• easy to comprehend, thx

• Combine the ideas of counting the length then modify k to k%n when k > n and not counting the length when there is no need for k < n. The runtime does not improve for the testcases, so just share the idea not the solution.

``````ListNode* rotateRight(ListNode* head, int k) {
// use pointer to pointer for easily rotate list
for(int i = 0; i < k; ++i){
fast = &((*fast)->next);
if(*fast == NULL)
{   // when the first time fast pointer reach the end, we know k at least n (length n = i + 1), so reset fast pointer to head and modify the loop control to k%length, so that this loop will run not more than twice.
unsigned length = i+1;
i = -1;
k %= length;
}
}
// if we out of the loop with fast pointer = head, we know k%length = 0, so there is no need to rotate, just return head
// the left move is the same with others
while((*fast)!= NULL) {
fast = &((*fast)->next);
slow = &((*slow)->next);
}
*slow = NULL;
}
``````

• Here is my solution, which doesn't need to count the length of the list first. Just use faster pointer and slower pointer method, when moving the faster pointer and k is larger than the length of the list, make k = k%length and move from head again. So even if k is far larger than list length, we will go through the list for no more than twice

``````ListNode* rotateRight(ListNode* head, int k) {
for(int i=0;i<k;i++){ // move the faster pointer for k steps first
if(p1->next) p1 = p1->next;
else{
k = k%(i+1);//if k is greater than the length of the list, make k = k%length
i = -1; // and count from the beginning again
}
}
while(p1->next!=NULL){
p1 = p1->next;
p2 = p2->next;
}
p2->next = NULL;
}
``````

• I'm agree with @carterbao . And here is my python solution.

``````class Solution(object):
if k == 0 or not head:
count = 1
while right.next and count <= k: # make right go k steps first
count += 1
right = right.next
if count <= k: # if k is larger the the length, make new k
while right.next:
right = right.next
left = left.next
sentry = left.next
left.next = None
return sentry
``````

• ``````public ListNode rotateRight(ListNode head, int n) {
if (head == null || head.next == null || n == 0) {
}
for (int i = 0; i < n; i++) {
if (fast.next == null) {
} else {
fast = fast.next;
}
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = null;
}
``````

This is my solution without counting the length. The trick is that when n > length, you put fast back to head. :)

It's a O(k) solution, it's not optimized when k is large. Here is my solution:

``````class Solution(object):
"""
:type k: int
:rtype: ListNode
"""
return
dis=0
while node.next and dis<k:
node=node.next
dis+=1
if dis==k: