# Ac solution code

• Solution1. Non-Recursive Solution - Special thanks for StefanPochmann's comment

``````  Assuming we have a linkedList: A..B..C..D:

Say A..B is a k-Group,

We need 3 steps to reverse the k-Group:
1) Find the kth node B (tail)
2) B..A  C..D: reverse A..B to B..A
3) B..A..C..D: connect the new tail A with the next head C

Keep the above steps, util it reaches the end of the linkedList.
``````

JAVA Code:

``````public ListNode reverseOneGroup(ListNode head, ListNode nextHead) {// Reverse one k-group
ListNode prev = null;
ListNode tmp = head.next;
}
return prev;
}

public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummyHead = new ListNode(0);
ListNode lastTail = dummyHead;
ListNode cur = head;

while (cur != null) {
int count = 0;
while (cur != null && count < k-1) {// Find the tail of the current k-group
count++;
cur = cur.next;
}
if (cur == null) break;// Reached the end: the remaining nodes are less than k

cur = cur.next;// Next head
lastTail.next = reverseOneGroup(head, cur);// lastTail: connect with the new head after reversal
head.next = cur;// curTail: connect with the next head. (head is reversed to the current tail)
}
}
``````

Solution2. Recursive Solution - Special thanks to @shpolsky

As only constant memory is allowed, recursive solution actually doesn't satisfy the requirement, because it needs system stack space for recursion.

``````1) Find kth node (Next head after k-group)
2) Reverser k..end-1 as the next node of 0..k-1(k-group)
3) Reverse 0..k-1(k-group)
4) Keep the above steps recursively
``````

Time Complexity: O(n)

``````1) For each k-Group, we need O(k)(Find kth node) + O(k)(Reverse k nodes)=O(2k)=O(k)
2) There're (n / k) groups totally
So the total time complexity = O(k) * (n / k) = O(k * (n / k)) = O(n).
``````

JAVA Code:

``````public ListNode reverseKGroup(ListNode head, int k) {
for (int i = 0; i < k; i++) { //Find the next head after k-group (kth node, because k-group is 0..k-1)
if (nextHead == null) return head;// less than k nodes left, return the orginal head
}

ListNode previousTail = head;// head of (0..k-1)group becomes the previous tail of (k..n)group

// reverse 0..k-1
ListNode prev = null;
for (int i = 0; i < k; i++) {
ListNode next = head.next;
head.next = prev;// point head.next back to previous
prev = head;// update current 'prev'
}

// Append result of (k..n) nodes to (0..k-1) group
previousTail.next = reverseKGroup(nextHead, k);

return prev;
}
``````

• "Only constant memory is allowed."

• Haha, didn't notice that, gonna modify it to non-recursive ;) Thanks, buddy!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.