# Leetcode top 100 raised questions 25. Reverse nodes in k-group (Java version; Hard)

## Leetcode top 100 raised questions 25. Reverse nodes in k-group (Java version; Hard)

#### Title Description

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

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

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

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

Note:

Only constant extra memory is allowed.
You may not alter the values in the list's nodes, only nodes itself may be changed.
```

#### The first time; recursion, the core is recursive function logic: start from the head, reverse k nodes, and connect with the next section (the new condition hidden in this sentence is new recursion), and finally return to the head node

```//This problem is very recursive; each section is processed in the same way, but how to write it? What is the logic of recursive function?
class Solution {
//Recursive function logic: start from head, reverse k nodes, and connect with the next section (New recursion hidden in this sentence), and finally return to the head node
public ListNode reverseKGroup(ListNode head, int k) {
//base case
//
//Determine whether there are k nodes
int n = 0;
while(cur!=null){
n++;
if(n==k)
break;
cur = cur.next;
}
//If it is less than k nodes, it does not need to flip and directly returns to the head node
if(n<k)
//Length enough k, reverse the list
//First save the head node of the next link list to be reversed
ListNode left=null, right;
for(int i=0; i<k; i++){
//save next
right = cur.next;
//change
cur.next = left;
//update
left = cur;
cur = right;
}
//The tail of the reversed linked list connects the new head of the next link to be reversed
//Returns the header of the current segment
return left;
}
}
```

#### Do it for the first time; create a dummy node so you don't have to deal with it alone; be concise

```class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
//input check
//Create dummy nodes; treat dummy nodes as processed nodes
ListNode dummy = new ListNode(0);
//You need to know the tail after the previous reversal and the head of the next link list to be reversed
//Check whether the length is not less than k
int n = 0;
while(cur!=null){
cur = cur.next;
n++;
if(n==k)
break;
}
//If the length is less than k, there is no need to reverse
if(n<k)
break;
//Length not less than k, reverse operation
ListNode left=null, right;
for(int i=0; i<k; i++){
//save next
right = cur.next;
//change
cur.next = left;
//update
left = cur;
cur = right;
}
//update
//The tail of the previous section connects the head of the current section
preTail.next = left;
//Details: for the time being, if you jump out of the loop, you don't need to connect again
}
return dummy.next;

}
}
```

#### Do it for the first time; draw a picture; deal with it alone first, and then deal with the rest in a circular way; write it a little verbose, especially if it needs to be dealt with separately

```class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
//input check
int n=0;
while(cur!=null){
n++;
cur = cur.next;
}
if(n<k)
//Number of reversals
int times = n/k;
//Single reverse first
ListNode tail = res;
//Deal with the rest
for(int i=1; i<times; i++){
tail.next = tmp;
//update
tail = tmp;
}

}

//Return the reversed: 1. Head node 2. Tail node 3. Next node of the original tail node
private ListNode[] reverse(ListNode head, int k){
for(int i=0; i<k; i++)
//
while(k>0){
//save next
right = cur.next;
//change
cur.next = left;
//update
left = cur;
cur = right;
k--;
}
//1. 2. 3.
}
}
```

#### Excellent problem solving Recursive writing

```class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
int count = 0;
while (cur != null && count != k) {
cur = cur.next;
count++;
}
if (count == k) {
cur = reverseKGroup(cur, k);
while (count != 0) {
count--;  