Skip to content

Instantly share code, notes, and snippets.

@vo
Created February 12, 2014 02:43
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save vo/8949080 to your computer and use it in GitHub Desktop.
Save vo/8949080 to your computer and use it in GitHub Desktop.
Rotate N size list by K to the right in O(N) time, O(1) space.
#include <stdio.h>
#define N 20
#define K 5
// reverses letters in indices s[from:to]
void reverse_string(char * s, int from, int to)
{
char * p1 = s + from;
char * p2 = s + to;
while(p1 < p2) {
char c = *p1;
*p1 = *p2;
*p2 = c;
p1++;
p2--;
}
}
int main() {
char A[N];
int i;
// fill array with example letters
for(i=0; i<N; i++)
A[i] = i+'a';
// rotate string right by k
int amt = N % K;
reverse_string(A, 0, N-1);
reverse_string(A, 0, K-1);
reverse_string(A, K, N-1);
// print array to show output
for(i=0; i<N; i++)
printf("%c ", A[i]);
printf("\n");
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment