每k个节点反转链表（单链表）--数据结构--C语言算法_单链表每k个反转

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明：你的算法只能使用常数的额外空间。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

思路：例如有如下链表------------------------------------------------------------------

若此时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;
如图所示。

参考上述首次翻转，再次执行即可。

代码：

#include <stdlib.h>
#include <stdio.h>

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<n;i++)
    {
      q=(LNode *)malloc (sizeof(LNode));
      scanf ("%d",&q->data);
      p->next=q;  
      p=q;     
    }
    p->next=NULL;
   return head;
  }

int get_length(LNode *head){//求链表长度
    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<c;i++)
	{
		
		for(m=k-1;m>0;m--)//头插k-1次 
		{
			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<=%d)",get_length(head));
	scanf("%d",&k);
	head=fan(head,k);
	printf("  翻转后:");
	print(head);
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97