### welcome to my blog

## 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: 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 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 if(head==null || head.next==null || k<=1) return head; // //Determine whether there are k nodes int n = 0; ListNode cur=head; 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) return head; //Length enough k, reverse the list //First save the head node of the next link list to be reversed ListNode nextHead = cur.next; ListNode left=null, right; cur = head; 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 head.next = reverseKGroup(nextHead, k); //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 if(head==null || head.next == null || k<=1) return head; //Create dummy nodes; treat dummy nodes as processed nodes ListNode dummy = new ListNode(0); dummy.next = head; //You need to know the tail after the previous reversal and the head of the next link list to be reversed ListNode preHead = dummy, preTail = dummy, nextHead = head; while(nextHead!=null){ //Prepare to reverse the link list at the beginning of nextHead ListNode cur = nextHead; //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; cur = nextHead; 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; preTail = nextHead; nextHead = cur; //Details: for the time being, if you jump out of the loop, you don't need to connect again preTail.next = nextHead; } 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 if(head==null || head.next==null) return head; //Length of statistical link list int n=0; ListNode cur=head; while(cur!=null){ n++; cur = cur.next; } if(n<k) return head; //Number of reversals int times = n/k; //Single reverse first ListNode[] res = reverse(head, k); //Head to return ListNode newHead = res[0]; ListNode tail = res[1]; ListNode nextHead = res[2]; //Deal with the rest for(int i=1; i<times; i++){ ListNode[] tmp = reverse(nextHead, k); //Old tail connects new head tail.next = tmp[0]; //update tail = tmp[1]; nextHead = tmp[2]; } tail.next = nextHead; return newHead; } //Return the reversed: 1. Head node 2. Tail node 3. Next node of the original tail node private ListNode[] reverse(ListNode head, int k){ ListNode nextHead = head; for(int i=0; i<k; i++) nextHead = nextHead.next; // ListNode left=null, cur=head, right; while(k>0){ //save next right = cur.next; //change cur.next = left; //update left = cur; cur = right; k--; } //1. 2. 3. return new ListNode[]{left, head, nextHead}; } }

#### Excellent problem solving Recursive writing

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