[leetcode] a group of K flipped linked lists

#LeetCode A daily topic 【 Special topic of linked list 】

• K A set of flip list
  https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
• analysis
  According to the given k value , Group and reverse the original linked list , The remaining deficiency k It's the same
  My first idea is to find out the length of the linked list , Then calculate the number of groups according to the length , Then reverse each group , Finally, they can be spliced together
• Realization

public ListNode reverseKGroup(ListNode head, int k) {
    
        int length = 0;
        ListNode temp = head;
        while (temp != null) {
    
            temp = temp.next;
            length++;
        }
        int count = length / k;
        ListNode ans = new ListNode(0);
        ListNode node = ans, prev = null, next;
        for (int i = 0; i < count; i++) {
    
            //  Record the first element before reversing the linked list , That is, the last element after inversion （ Commonly used for splicing ）
            temp = head;
            for (int j = 0; j < k; j++) {
    
                next = head.next;
                head.next = prev;
                prev = head;
                head = next;
            }
            node.next = prev;
            // node Point to temp, That is, let it point to the last node after inversion , Facilitate splicing 
            node = temp;
            //  Reset prev
            prev = null;
        }
        node.next = head;
        return ans.next;
    }

LeetCode Time consuming ：0ms

• Achieve two
  Consolidate the recursive algorithm routine learned before , I also wrote a recursive algorithm ：
  Every time K A group of the original linked list is divided into , Continuous recursion , Until the linked list is empty or short k Recursion ends ;
  Based on the current recursion , Reverse the current linked list to the result returned in the previous step of splicing
• Recursive implementation

public ListNode reverseKGroup02(ListNode head, int k) {
    
        if (head == null) {
    
            return null;
        }
        ListNode node = head;
        for (int i = 0; i < k - 1; i++) {
    
            node = node.next;
            //  Insufficient length of linked list k
            if (node == null) {
    
                return head;
            }
        }
        ListNode p = node.next;
        node.next = null;
        ListNode ans = reverseKGroup02(p, k);
        //  Reverse the standard template ,prev It is the result of inversion 、head Is the last value after inversion 
        ListNode prev = null, next, q = head;
        while (q != null) {
    
            next = q.next;
            q.next = prev;
            prev = q;
            q = next;
        }
        head.next = ans;
        return prev;
    }

LeetCode Time consuming ：0ms

• summary
  This problem belongs to the deformation problem of reverse linked list , Can skillfully use the operation of reverse linked list should be very easy to solve ; For recursive methods , Or the trilogy mentioned before ： Find end condition , Find the return value , What recursion can get and what it should do