将单链表的每K个结点逆序

问题重述：给定一个单链表的头节点，实现一个调整单链表的函数，使得每k个结点之间逆序，如果最后不足k个节点一组则不调整最后几个结点

问题分析：

简单做法，直接使用栈保存那k个结点，然后将这k个结点逆序后连接到链表上去，只需要注意头节点即可。进阶解法直接对链表进行处理，每一次记录当前逆序分组的第一个结点和最后一个结点，也需要考虑头节点

解法：

使用栈、直接对链表进行迭代

解题：

代码：

普通：

public static Node reverseKNode1(Node head,int k) {
		if(k < 2) {
			return head;
		}
		Stack<Node> stack = new Stack();
		Node newHead = head;
		Node cur = null;
		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;
	}
	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;
	}

进阶

	public static Node reverseKNode2(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);
				count = 0;
			}
			count++;
			cur = next;
		}
		return head;
	}
	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;
	}

总结：

当遇见对某几个结点进行处理的时候，我们就可以使用容器来装这几个结点，然后处理完成后在加回原来的链表中