“This is the sixth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

[B] [C] [D]

You are given a linked list, each k nodes in a group of flipped, please return to the flipped list.

K is a positive integer whose value is less than or equal to the length of the list.

If the total number of nodes is not an integer multiple of k, keep the last remaining nodes in the same order.

Advanced:

  • Can you design an algorithm that only uses constant extra space to solve this problem?
  • You can’t just change the values inside the nodes, you need to actually swap nodes.

Example 1:

Input: head = [1,2,3,4,5], k = 2 output: [2,1,4,3,5]Copy the code

Example 2:

Input: head = [1,2,3,4,5], k = 3 output: [3,2,1,4,5]Copy the code

Example 3:

Input: head = [1,2,3,4,5], k = 1 output: [1,2,3,4,5]Copy the code

Example 4:

Input: head = [1], k = 1 output: [1]Copy the code

Tip:

  • The number of nodes in the list is in the rangesz 内
  • 1 <= sz <= 5000
  • 0 <= Node.val <= 1000
  • 1 <= k <= sz

The answer to this question is as follows:

  1. ifk = 1At this time, each node is flipped as a group. The flipped linked list is the same as the original linked list, so we directly returnheadCan be
  2. Walk through the list, if you findkAnd flip them as a group, if there are not enough nodeskA, returnheadCan be
  3. The second step operation of the remaining linked list is carried out recursively, and the head node of the subsequent flipped linked list is connected to the tail node of the previous flipped linked list, until the whole list is traversed

The operation of linked lists is relatively complicated. The code is as follows:

Var reverseKGroup = function(head, k) {if(k===1) return head; / / flip function function reverse (head, k) {if (head = = = null | | head. The next = = = null) return the head; // let pre = head,next = head. Next, CNT = K; while(cnt&&next){ cnt--; // Point next's pre property to its previous node in preparation for flipping the list next. pre = pre.next; next = next.next; } // return head if(CNT) return head; Const nextHead = next, vhead = new ListNode(0); next = pre,pre = head; vhead.next = next; // flip the list while(next! ==pre){ next.next = next.pre; next = next.pre; Next = reverse(nextHead,k) // Return vhead.next; // return vhead. } // return reverse(head,k-1); };Copy the code

If you have any questions or suggestions, please leave a comment!