25. Flip linked lists in groups of K

This is the 13th day of my participation in the August More Text Challenge

25. Flip linked lists in groups of K

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] example 2:

Input: head = [1,2,3,4,5], k = 3 output: [3,2,1,4,5] example 3

Input: head = [1,2,3,4,5], k = 1 Output: [1,2,3,4,5] Example 4:

Input: head = [1], k = 1 Output: [1] Hint:

The number of nodes in the list is within the range sz 1 <= sz <= 5000 0 <= node. val <= 1000 1 <= k <= sz

Their thinking

Reuse the function used when flipping linked lists to complete the flipping of a set of nodes

Through traversing the linked list, find the beginning and end nodes of each group of linked lists, cut this section of linked list from the original linked list, but record the cutting point of the original linked list, in order to reconnect the flipped linked list back to the original list.
If k nodes are flipped each time and the length of the current linked list is found to be less than K when traversing the nodes, it indicates that this is the last linked list whose length is less than K, and it does not need to be flipped and can be returned directly

code

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; }} * * /
public class Solution {
    / * * * *@paramThe head ListNode class *@paramK int Int *@returnListNode class * /
    public ListNode reverseKGroup (ListNode head, int k) {
        if(head==null||head.next==null||k==1) return head;
        ListNode dumpy=new ListNode(-1),pre=dumpy;
        dumpy.next=head;
        while(true)
        {
            ListNode h=pre.next,tail=pre.next;
            if(tail==null)
                    return dumpy.next;
            for(int i=0; i<k-1; i++) { tail=tail.next;if(tail==null)
                    return dumpy.next;
            }
            ListNode npre=tail.next;
            tail.next=null;
            pre.next=null;
            reverseList(h);
            pre.next=tail;
            h.next=npre;
            pre=h;

        }
      
            // write code here
    }
     public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        ListNode pre = head, next = head.next;
        pre.next = null;
        while(next ! =null) {
            ListNode nx = next.next;
            next.next = pre;
            pre = next;
            next = nx;
        }
        returnpre; }}Copy the code

25. Flip linked lists in groups of K