链表中的节点每k个一组翻转

1.借助栈（利用后进先出的特点进行反转）
时间复杂度：O（n2），如果反转长度刚好为整个链表，循环就会达到n2；空间复杂度：O（n），借助了栈。
import java.util.*;

/*

• public class ListNode {
• int val;
• ListNode next = null;
• }
• /

public class Solution {
/*
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode reverseKGroup (ListNode head, int k) {
// write code here
if(head==null||k==1||head.next==null)
return head;
Stack<listnode> s1=new Stack<>();
int num=0;
ListNode res=null;
while(head!=null){
s1.push(head);
head=head.next;
num++;
if(num==k){//每当链表个数满足k个时，进行反转
for(int i=0;i<num;i++){
ListNode temp=s1.pop();
temp.next=res;
res=temp;
}
num=0;
}
}
Stack<listnode> s2=new Stack<>();
while(!s1.empty()){//最后几个不满足k个不用反转，要变成正常顺序
s2.push(s1.pop());
}
while(!s2.empty()){//插入最后几个
ListNode temp=s2.pop();
temp.next=res;
res=temp;
}
ListNode res1=null;
while(res!=null){//因为用的是尾插法，所以还需整个链表进行反转一次
ListNode temp=new ListNode(res.val);
temp.next=res1;
res1=temp;
res=res.next;
}
return res1;
}
}
2.利用头插法
时间复杂度：o（n2）；空间复杂度：O（1）
import java.util.</listnode></listnode>;

/*

• public class ListNode {
• int val;
• ListNode next = null;
• }
• /

public class Solution {
/*
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode reverseKGroup (ListNode head, int k) {
// write code here
if(head==null||k==1||head.next==null)
return head;
int length=0;
ListNode res=new ListNode(0);//创建一个头结点
res.next=head;
ListNode pre=res,cur=head,temp=null;
while(head!=null){//计算链表的总长度
length++;
head=head.next;
}
//利用头插法完成反转
for(int i=0;i<length/k;i++){
for(int j=1;j<k;j++){
temp=cur.next;
cur.next=temp.next;
temp.next=pre.next;
pre.next=temp;
}
pre=cur;
cur=cur.next;
}
return res.next;
}
}
3.递归
每k个结点进行一次递归，时间复杂度：O（n2），取k个结点加对k个结点进行递归反转；空间复杂度：O（n），递归栈的深度。
import java.util.;

/*

• public class ListNode {
• int val;
• ListNode next = null;
• }
• /

public class Solution {
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode reverseKGroup (ListNode head, int k) {
// write code here
if(head==null||k==1||head.next==null)
return head;
ListNode tail=head;
for(int i=0;i<k;i++){
if(tail==null)//反转个数不够k个
return head;
tail=tail.next;
}
ListNode res=reverse(head,tail);
head.next=reverseKGroup(tail,k);//下一次开始反转起点为tail
return res;
}
public ListNode reverse(ListNode head, ListNode tail) {//反转head到tail的数据
ListNode pre=null,next=null;
while(head!=tail){
next=head.next;
//尾插法进行反转
head.next=pre;
pre=head;
head=next;
}
return pre;
}
}