[算法] 将单链表的每K个节点之间逆序

题目

给定一个单链表的头结点，实现一个调整单链表的函数，使得每K个节点之间逆序，如果最后不够K个节点一组，则不调整最后几个节点。

解答

使用栈结构

import java.util.Stack;

 public class Test{

 static class Node{

	public int val;

	public Node next;

	public Node(int val){

		this.val=val;

	}

}

public static void main(String[] args) {

	Node head=new Node(1);

	head.next=new Node(2);

	head.next.next=new Node(3);

	head.next.next.next=new Node(4);

	head.next.next.next.next=new Node(5);

	head.next.next.next.next.next=new Node(6);

	Node node=reverseKNodes(head,2);

	while(node!=null){

		System.out.print(node.val+" ");

		node=node.next;

	}

}

public static Node reverseKNodes(Node head, int K){

	if (K<2) {

		return head;

	}

	Stack<Node> stack=new Stack<>();

	Node newHead=head;

	Node cur=head;

	Node pre=null;

	Node next=null;

	while(cur!=null){

		stack.push(cur);

		next=cur.next;

		if (stack.size()==K) {

			pre=resign(stack,pre,next);

			newHead=newHead==head?cur:newHead;

		}

		cur=next;

	}

	return newHead;

}

public static Node resign(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;

}

 }

不使用栈结构

import java.util.Stack;

public class Test{

 static class Node{

	public int val;

	public Node next;

	public Node(int val){

		this.val=val;

	}

}

public static void main(String[] args) {

	Node head=new Node(1);

	head.next=new Node(2);

	head.next.next=new Node(3);

	head.next.next.next=new Node(4);

	head.next.next.next.next=new Node(5);

	head.next.next.next.next.next=new Node(6);

	Node node=reverseKNodes(head,2);

	while(node!=null){

		System.out.print(node.val+" ");

		node=node.next;

	}

}

public static Node reverseKNodes(Node head, int K){

	if (K<2) {

		return head;

	}

	Node cur=head;

	Node pre=null;

	Node next=null;

	Node start=null;

	int count=1;

	while(cur!=null){

		next=cur.next;

		if (count==K) {

			start=pre==null?head:pre.next;

			head=pre==null?cur:head;

			resign(pre,start,cur,next);

			pre=start;

			count=0;

		}

		count++;

		cur=next;

	}

	return head;

}

public static void resign(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;

}

}