Reverse Nodes in k-Group @LeetCode

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

	package leetcode.linkedlist;
	/**
	* Solution: 拆分group, 每个group上reverse, 思路并不难，但是实现起来挺麻烦，
	* 每一段需要currentHead, currentTail 做标记用于后面的链接. 还有preTail. 另外reverse过程中需要preNode和nextNode
	* 有时候忘记这些flag就不容易一下子写出来，所以要按功能记，reverse需要2个，连接时候需要3个.
	* @author jeffwan
	* @date Apr 15, 2014
	*/
	public class ReverseKGroup {
	public ListNode reverseKGroup(ListNode head, int k) {
	if (head == null || k <= 1) {
	return head;
	}
	int length = getLength(head);
	int group = length / k;
	if (group == 0) {
	return head;
	}
	ListNode current = head;
	ListNode preTail = null, currentHead = null, currentTail = null;
	ListNode preNode = null, nextNode = null;
	for (int i = 0; i < group; i++) {
	preNode = null;
	for (int j = 0; j < k; j++) {
	// Reverse
	if (current != null) {
	nextNode = current.next;
	current.next = preNode;
	preNode = current;
	}
	// Assign currentHead, currentTail for future concatenate.
	if (j == 0) {
	currentTail = current;
	}
	if (j == k - 1) {
	currentHead = current;
	}
	current = nextNode;
	}
	if (preTail == null) {
	head = currentHead;
	} else {
	preTail.next = currentHead;
	}
	preTail = currentTail;
	}
	currentTail.next = current;
	return head;
	}
	public int getLength(ListNode head) {
	int length = 0;
	while (head != null) {
	head = head.next;
	length++;
	}
	return length;
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) { this.val = x; }
	}
	}

view raw ReverseKGroup.java hosted with ❤ by GitHub