25. Flip linked lists in groups of K

It’s actually a simulation, but as we described earlier, simulation is the same thing as expressing the algorithm.

In order to express and write the algorithm, we need to model: in the model we prove correct to carry out various definitions, and then need to ensure that in the process of solving the model always meet the requirements of the model, so we can divide this problem into the following steps:

  1. Our main function calls the function that rotates k nodes
  2. Define a function to rotate k nodes: invert k nodes after pre and return the last of k, or null if there are less than k nodes
    • So once I get pre, I’m going to split the next list into three sections,Splitting into three segments requires that each of the segments meet the criteria for a separate list, i.e. the end of the list is null:
      • 1. Previous paragraph: paragraph with Pre
      • 2. Current segment: k nodes after Pre
      • 3. Next segment: the segment starting from the k+1 node after pre
    • After splitting into three segments, all we need to do is head insert the current segment into the previous segment
    • The last thing you need to do is connect the last element of the previous segment to the last element of the next segment

When we write a problem, it’s a matter of whether it’s difficult or not, but if we do, we need to define the problem space, the answer space, the constraints that we meet in the process, that’s the foundation of our bug reduction code.

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode ret = pre;
        while(pre ! =null) {
            pre = reverseKNode(pre, k);
        }
        return ret.next;
    }
    /* * reverses k after pre and returns the last of k, or null * */ if there are less than k
    public ListNode reverseKNode(ListNode pre, int k) {
        if (pre == null || pre.next == null) return null;
        ListNode temp = pre, ret = pre.next, next = null;
        int count = 0;
        while(temp ! =null && count < k) {
            count++;
            temp = temp.next;
        }
        if (count < k || temp == null) return null;
        next = temp.next;// Get the start of the next paragraph
        temp.next = null;// Clear the end of the current paragraph

        // Process the current segment and split the current segment from the previous segment
        temp = pre.next;

        // Set pre to the previous paragraph
        pre.next = null;
        while(temp ! =null) {
            ListNode node = temp.next;
            temp.next = pre.next;
            pre.next = temp;
            temp = node;
        }
        ret.next = next;
        return ret;
    }
Copy the code