数据结构与算法Java版：链表每K个节点一组进行翻转

题目描述：给定一个含有 n 个元素的链表，现在要求每 k个节点一组进行翻转，打印翻转后的链表结果。其中，k是一个正整数，且可被 n 整除。例如，链表为 1 -> 2 -> 3 -> 4 -> 5 -> 6，k= 3，则打印 321654。

方法一

算法还是链表翻转的算法。利用 3 个指针，prev、curr、next，执行链表翻转，每次得到了 k个翻转的结点就执行打印。由于翻转后的链表会不断变长，所以我重写一个打印函数，每次只打印前k个。

public class LinkedList {
	Node head;
	public static void main(String[] args) {
		LinkedList list = new LinkedList();
		list.add(6);
		list.add(5);
		list.add(4);
		list.add(3);
		list.add(2);
		list.add(1);
		System.out.println("原始链表：");
		printList(list.head);
		System.out.println("\n每3个节点一组进行翻转：");
		reverseK(list.head, 3);
	}

	// 头插法建立链表，头节点不为空
	public void add(int num) {
		Node node = new Node(num);
		if (this.head == null) {
			this.head = node;
		} else {
			node.next = this.head;
			this.head = node;
		}
	}

	// 链表每K个节点一组翻转
	public static void reverseK(Node head, int k) {
		Node pre = null;
		Node next = null;
		int i = 1;
		int L = length(head);
		while (i <= L) {
			next = head.next;
			head.next = pre;
			pre = head;
			head = next;
			if (i % k == 0) {
				printList2(pre, k);
			}
			i++;
		}
	}

	public static void printList(Node p) {
		while (p != null) {
			System.out.printf("%d ", p.val);
			p = p.next;
		}
	}

	public static void printList2(Node p,int k) {
		int i=0;
		while (i<k) {
			System.out.printf("%d ", p.val);
			p = p.next;
			i++;
		}
	}
	public static int length(Node head) {
		Node p = head;
		int i = 0;
		while (p != null) {
			i++;
			p = p.next;
		}
		return i;
	}
}

class Node {
	public Node[] p2;
	int val;
	Node next = null;

	public Node() {

	}

	public Node(int val) {
		this.val = val;
	}
}

输出：

方法二

用到了栈就非常简单了。每次把k个节点push进去，然后pop出来即可。

public static void reverseK2(Node head, int k) {
		int i = 1;
		int L = length(head);
		Stack<Integer> stack = new Stack<Integer>(); // 创建堆栈对象
		while (i <= L) {
			stack.push(head.val); 
			head=head.next;
			if (i % k == 0) {
				while (!stack.empty()) {
					Integer t = (Integer) stack.pop();
			        System.out.print(t+" ");
				}
			}
			i++;
		}
	}