旋转链表
开头:
对于链表的建立已经熟悉,那我们现在讲讲旋转链表的如何实现,当然旋转链表的建立是在已经掌握普通链表的基础上讲解。
正文:
旋转链表,顾名思义就是让链表“动起来”。即:使链表尾部最后的结点转到链表首部的位置。假设已经建立好一条6个结点的链表,它的初始状态如下图:
我们让他旋转两次就变成了这样,其过程是这样的,先让103到首部,然后再让22到首部,这样就是旋转两次后的结果。
如果我们让其旋转 k次,$k = 2*10^{12}$,最后的结果是怎样的呢?即,k mod n,其中n是链表结点的个数。
下面我们来看代码:
void Linklist::Revolve(int ck,int cmaxn){count = 0;int count2 = 0;//创建四个指针Node *q1 = new Node;Node *q2 = new Node;Node *q3 = new Node;Node *q4 = new Node;q1 = first->next;q2 = first->next; q3 = first->next; q4 = first->next;int temp = cmaxn - ck;//q1的变化while(count != temp ){count++;q1 = q1->next; }//q2的变化q2 = q1;while(count2 != ck - 1){count2++;q2 = q2->next;}//q3的变化count = 0; while(count != temp - 1){count++;q3 = q3->next;}q3->next = q2->next;first->next = q1;q2->next = q4; }
上图中的图就是代码中的4个指针。指针指向的变化如下图:
、