字符串向左旋转

题目描述

给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的2个字符“ab” 移动到字符串的尾部，即变成“cdefab”。请写一个函数完成此功能，要求对长度为n的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。

在不考虑时空复杂度情况下，这个题目有最简单的两个解决方法。

1.将字符串的前i个元素复制到一个临时数组中，将于下的元素移动到指定位置，最后将最初的i个元素复制到余下位置。

2.定义一个函数向左旋一个位置，然后调用该函数i次。

这两个朴素的方法都无法达到题目要求的时空复杂度，所以需要考虑新的思路。

将一个字符串分成X和Y两个部分，在每部分字符串上定义反转操作，如X^T，即把X的所有字符反转（如，X="abc"，那么X^T="cba"），那么就得到下面的结论：(X^TY^T)^T=YX。显然这解决了字符串的反转问题。

例如字符串 abcdef ，若要让def翻转到abc的前头，只要按下述3个步骤操作即可：

首先分为俩部分，X:abc，Y:def；
将X反转，X->X^T，即得：abc->cba；将Y反转，Y->Y^T，即得：def->fed。
反转上述得到的结果字符串X^TY^T，即字符串cbafed的两部分（cba和fed）给予反转，得到：cbafed->defabc，形式化表示为(X^TY^T)^T=YX，这就实现了整个反转。

#include <iostream>
using namespace std;

void reverse(char *str,int start,int end)
{
 while (start<end)
 {
  char temp=str[start];
  str[start++]=str[end];
  str[end--]=temp;
 }
}

void rotateString(char *str,int m,int n)
{
 m=m%n;
 reverse(str,0,m-1);
 reverse(str,m,n-1);
 reverse(str,0,n-1);
}

int main()
{
 char str[]="abcdefg";
 rotateString(str,3,strlen(str));
 cout<<str<<endl;
}

这个题目的扩展到链表上。

链表翻转。给出一个链表和一个数k，比如链表1→2→3→4→5→6，k=2，则翻转后2→1→6→5→4→3，若k=3,翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→6→5。

#include <iostream>
using namespace std;
typedef struct NODE{
 int value;
 struct NODE *link;
}Node;

/* 
 检验链表插入正确性三步就是：
 先检查链表为空插入，然后是最普通中间插入，插入元素在最后，
 尤其注意在表头表尾插入情况
*/
void list_insert1(Node **rootp,int new_value)
{
 Node *current,*pre,*newNode;
 current=*rootp;
 pre=NULL;
 while (current!=NULL&¤t->value<new_value)
 {
  pre=current;
  current=current->link;
 }
 newNode=new NODE;
 if (newNode==NULL)
 {
  cerr<<"new fault \n";
 }
 newNode->value=new_value;
 newNode->link=current;
 if (pre==NULL)
 {
  *rootp=newNode;
 }
 else
  pre->link=newNode;
}

/*
 上面的插入需要每次单独考虑到 pre==NULL 这个情况，
 也就是单独考虑链表插入时是否为空。其实有方法把所有问题统一到一起解决
 前面插入需要设定pre变量，其实我们可以取得每个结点link域的地址，省去设定pre变量然后去
 进行单独情况考虑
*/
void list_insert2(Node **linkp,int new_value)
{
 Node *current,*new_Node;
 while ((current=*linkp)!=NULL&¤t->value<new_value)
 {
  linkp=¤t->link;
 }
 new_Node=new Node;
 if (new_Node==NULL)
 {
  cerr<<"new fault \n";
 }
 new_Node->value=new_value;
 new_Node->link=current;
 *linkp=new_Node;
}
//前面两种插入都是类似插入排序，进行有序插入，简单实现无序插入,每次插在root后面即为第一个结点
void list_insert3(Node **rootp,int new_value)
{
 Node *new_Node;
 new_Node=new Node;
 if (new_Node==NULL)
 {
  cerr<<" new fault \n";
 }
 new_Node->value=new_value;
 new_Node->link=*rootp;
 (*rootp)=new_Node;
}

void print_list(Node *root)
{
 //传入root 不会改变main中root指针，指针也是传值传递的
 cout<<"print list elemnet \n";
 if (root==NULL)
 {
  cout<<"empty list \n";
  return ;
 }
 while (root!=NULL)
 {
  cout<<root->value<<" ";
  root=root->link;
 }
 cout<<endl;
}

/*
 传入链表头尾指针实现链表逆置
*/
Node *reverseLinklist(Node *head,Node *tail)
{
 Node *current,*pre=NULL,*next;
 for (current=head;current!=tail;current=next)
 {
  //必须先记录current的下个位置！！
  next=current->link;
  current->link=pre;
  pre=current;
 }
 return pre;
}
/*
 传入需要开始左旋的位置K
*/
Node *leftRotate(Node *head,int k)
{
 Node *head1=NULL,*p=head;
 int count=0;
 while (p!=NULL)
 {
  count++;
  p=p->link;
  if (count>=k)
  {
   break;
  }
 }
 if (p==NULL)
 {
  cout<<"输入旋转参数错误\n";
  exit(1);
 }
 head1=p;
 //记录左旋后的链表头指针
 Node *root=reverseLinklist(head,p);
 //两个链表连接起来
 head->link=reverseLinklist(head1,NULL);
 return root;
}
int main()
{
 int a[]={6,5,4,3,2,1};
 Node *root=NULL;
 /*
  带头结点的链表操作，root为指向第一个结点的指针
  带头结点也就是花费一个指针root来指向链表第一个结点，
  方便每次查找到链表起始位置。
 */
 for (int i=0;i<6;i++)
 {
  //list_insert1(&root,a[i]);
  //list_insert2(&root,a[i]);
  list_insert3(&root,a[i]);
 }
 print_list(root);
 print_list(leftRotate(root,3));
 return 0;
}