每k个节点反转链表（单链表） |
您所在的位置：网站首页 › 链表反转k › 每k个节点反转链表（单链表） |
每k个节点反转链表（单链表）
|
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 示例： 给你这个链表：1->2->3->4->5 当 k = 2 时，应当返回: 2->1->4->3->5 当 k = 3 时，应当返回: 3->2->1->4->5 说明：你的算法只能使用常数的额外空间。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。 思路：例如有如下链表------------------------------------------------------------------
代码： #include #include typedef int datatype; typedef struct node{ datatype data; struct node *next; }LNode; LNode *create(int n);//建表 int get_length(LNode *head);//长度 void print(LNode *head);//打印 LNode *fan(LNode *head,int k);//翻转 LNode *create(int n){//建表 LNode *head,*p,*q; int i; head=(LNode *)malloc (sizeof(LNode)); p=head; printf (" 请输入%d个值:",n); for (i=0;i//求链表长度 LNode *p; int n=0; p=head; while (p->next!=NULL) { n++; p=p->next; } return n; } void print(LNode *head){ //打印链表 LNode *p=head; printf("\n -------打印-------\n"); while(p->next!=NULL) { p=p->next; printf(" %d",p->data); } printf("\n ------------------\n"); } LNode *fan(LNode *head,int k){ //翻转 int n=get_length(head); //定义n为链表长度 int m,i; //m用来限制头插节点的个数，每翻转一次需要头插k-1个节点 int c=n/k; //长度n除以每次翻转个数k，即一个链表需要翻转k个元素的次数 LNode *s,*p,*q; s=head; p=head->next; q=p->next; for(i=0;i p->next=q->next; q->next=s->next; s->next=q; q=p->next; } if(q!=NULL)//完成k个节点的翻转后，若还需翻转k个节点 { //则将指针指向下次操作的位置 q=q->next; s=p; p=p->next;} } return head; } main() { LNode *head=NULL; int n;//初始表长 printf(" 输入初始表长:"); scanf("%d",&n); head=create(n); print(head); int k;//翻转个数 printf(" 输入翻转个数k：(k>1且k |
若此时k=3，则我们只需要翻转123 456，7则保留不动 利用头插的话，首先是要将指针指向2的位置，将其移动到1之前，其次是将3移动到1之前，也就是移动两次（k-1次）。 此时我们利用三个指针，如下图所示。 
执行 p->next=q->next;实现将q指向的节点腾出后，使其插入到s之后，即： q->next=s->next; s->next=q; 实现2的头插后，执行q=p->next实现将指针q指向数据为3的节点，按照刚才头插2的方式，将3头插到s之后，就完成了第一次翻转k个节点。 如下图所示。 
此时，如果利用长度n除以翻转个数k可知需要翻转的次数。 若还需执行下一次翻转，则需要将三个指针指向指定位置，即: q=q->next; s=p; p=p->next; 如图所示。 
参考上述首次翻转，再次执行即可。【本文地址】