# Simple Java iterative solution with explanation

• The basic idea is for each step,we set the the node after `head` as the list's new head, so that `head` then is `tail`. After reversing k nodes, we update the references and iterate through the whole list. If the size of the list is a multiple of k, the list is safely returned. Otherwise, a recursive call is made on the left-out nodes to undo the reverse. So the whole iteration times will be `(n + n%k)`

Here is an example of how it works(case of K = 3):

Initial:

``````sentinel -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 ->...
|       |    |
``````

Set the node after tail @newHead as the new head. And the list:

``````sentinel -> 2 -> 1 -> 3 -> 4 -> 5 -> 6 ->...
|            |    |
``````

Set node after tail as new Head:

`````` sentinel -> 3 -> 2 -> 1 -> 4 -> 5 -> 6 ->...
|                  |
dummy               tail
``````

3 nodes are reversed. Update the references:

``````sentinel -> 3 -> 2 -> 1 -> 4 -> 5 -> 6 ->...
|    |    |
``````

Here is code:

``````public ListNode reverseKGroup(ListNode head, int k) {
ListNode sentinel = new ListNode(0);
While (true) {
int count = k - 1;
while (count > 0) {
if (tail.next != null) {
count--;
} else {
/// list size is not multiple of k, a recursive call on the left-out nodes to undo the reverse
dummy.next = reverseKGroup(dummy.next, k - count);
return sentinel.next;
}
}
if (tail.next == null) return sentinel.next; /// list size is multiple of k, safely return
dummy = tail;
tail = tail.next;
}
}``````

• Very nice solution. But can you explain how the complexity is O(n + n%k); Also can you tell what is the complexity of my code.

Thank you.

`````` public static ListNode reverseKGroup(ListNode head, int k) {
}
ListNode slow = null, newHead = new ListNode(-1), pre = newHead, temp = null, cur = head;

while(cur != null) {
int i = 0;
temp = cur;
for(i = 0; cur != null && i < k; ++i) {
slow = cur;
cur = cur.next;
}
slow.next = null;

if(i < k) {
pre.next = temp;
}
else {
pre.next = reverseList(temp);
i = 0;
while(pre != null && i < k) {
pre = pre.next;
i++;
}
}
}
}

public static ListNode reverseList(ListNode head) {
ListNode reverse = null;
ListNode next = null;
}
return reverse;
}
``````

• Basically, my idea is to walk through the listnodes, while at the same time, reverse the nodes and keep counting the nodes reversed. Start the next round after reversing k nodes Group. When the number of the nodes n is a multiply of k, after N iteration, the list is k reversed. But when N is not a multiply of k, let's say to reverse 1 -> 2 -> 3 -> 4 -> 5 in 3 Group, after N iteration the list becomes 3 -> 2 -> 1 -> 5 -> 4. But the question requires "left-out nodes in the end should remain as it is". So a recursive call is made to undo the reverse of the left-out nodes. And there are n%k left-out nodes. So I said there will be (n + n%k) iterations.

Your idea is to firstly locate k nodes Group then reverse them, iteratively. Both your and my solution visit the nodes a constant of times, so using the big O notation, i think the complexity of both solutions are O(n), (only with difference up to a constant factor).

• Thanks for sharing, really helpful.

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