import java.util.Stack;
//将单链表的每k个节点之间逆序
public class ReverseKOfList{
//单链表节点的定义
public static class Node{
public int value;
public Node next;
public Node(int data)
{
this.value=data;
}
}
//(方法一、反转部分链表法)每k个节点之间逆序
public static Node ReverseK(Node head,int k)
{
if(head==null||k<=0)
{
return head;
}
if(k==1)
{
return head;
}
int n=0; //记录链经历的节点数
Node p=head; //记录链表的头节点
Node q=head;
int leng=0;
while(q!=null)
{
++leng;
q=q.next;
}
//n=(int)Math.floor(leng/k);
n=leng/k; //记录反转的次数
//System.out.println(n);
int from=1;
int to=k;
while(n>0)
{
Node mode=reverseSublist(head,from,to); //记录每次变换后的链表头节点
//PrintList(mode);
head=mode;
from+=k;
to+=k;
n--;
}
return head;
}
//反转部分链表
public static Node reverseSublist(Node head, int from,int to)
{
if(head==null||from <0||to<0)
{
return head;
}
Node p=head;
int leng=0;
Node tPre=null; //获取反转起始节点的前一个节点
Node tPos=null; //获取反转结束节点的后一个节点
//计算链表长度
while(p!=null)
{
++leng;
tPre=(leng==from-1?p:tPre); //找到反转起始节点的前一个节点
tPos=(leng==to+1?p:tPos); //找到反转结束节点的后一个节点
p=p.next;
}
if(from>leng||to>leng||from>to)
{
return head;
}
p=tPre==null?head:tPre.next; //找到要起始反转的节点
Node node2=p.next;
p.next=tPos; //起始反转的节点指向反转结束节点的后一个节点
Node next=null;
while(node2!=tPos)
{
next=node2.next;
node2.next=p;
p=node2;
node2=next;
}
if(tPre!=null)
{
tPre.next=p;
return head;
}
return p;
}
//(方法二、利用栈结构)每k个节点之间逆序
public static Node ReverseK2(Node head, int K) {
if (K < 2)
{
return head;
}
Stack<Node> stack = new Stack<Node>();
Node newHead = head; //记录新的头结点
Node cur = head;
Node pre = null;
Node next = null;
while (cur != null) {
next = cur.next;
stack.push(cur);
if (stack.size() == K) {
pre = resign1(stack, pre, next);
newHead = newHead == head ? cur : newHead;
}
cur = next;
}
return newHead;
}
//调整k个节点逆序
public static Node resign1(Stack<Node> stack, Node left, Node right) {
Node cur = stack.pop();
if (left != null) {
left.next = cur;
}
Node next = null;
while (!stack.isEmpty()) {
next = stack.pop();
cur.next = next;
cur = next;
}
cur.next = right;
return cur;
}
//(方法三、利用变量存储)每k个节点之间逆序
public static Node ReverseK3(Node head, int K) {
if (K < 2) {
return head;
}
Node cur = head;
Node start = null;
Node pre = null;
Node next = null;
int count = 1;
while (cur != null) {
next = cur.next;
if (count == K) {
start = pre == null ? head : pre.next;
head = pre == null ? cur : head;
resign2(pre, start, cur, next);
pre = start;
count = 0;
}
count++;
cur = next;
}
return head;
}
//调整k个节点逆序
public static void resign2(Node left, Node start, Node end, Node right) {
Node pre = start;
Node cur = start.next;
Node next = null;
//链表的逆转
while (cur != right) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
if (left != null) {
left.next = end;
}
start.next = right;
}
//打印链表
public static void PrintList(Node head)
{
while(head!=null)
{
System.out.print(head.value+" ");
head=head.next;
}
System.out.println();
}
public static void main(String[]args)
{
Node node=new Node(1);
node.next=new Node(2);
node.next.next=new Node(3);
node.next.next.next=new Node(4);
node.next.next.next.next=new Node(5);
node.next.next.next.next.next=new Node(6);
node.next.next.next.next.next.next=new Node(7);
node.next.next.next.next.next.next.next=new Node(8);
PrintList(node);
//Node mode=ReverseK(node,3); //时间、空间复杂度大
//Node mode=ReverseK2(node,3);//时间O(n),空间O(k)
Node mode=ReverseK3(node,3); //时间O(n),空间O(1)
PrintList(mode);
}
}
