This is the 22nd day of my participation in Gwen Challenge

preface

The reverse linked list of question 25 in a group of K is as follows:

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]

A, thinking

This problem can obviously be solved recursively, as the function itself only needs to handle the inversion of the first K nodes.

So how do you reverse the first K nodes of the current list? There are two ways to handle this:

1. The first K nodes are read and stored in the List, and the List is iterated to reconstruct the linked List
2. Use the head plug method to modify in place, no more storage space

The first implementation is relatively simple, and the code below should make sense. So here is a focus on using the head plug method to reverse linked lists

Tips: The headplug method does not require additional storage space and will perform faster! ⭐⭐⭐ is recommended

The idea of using the header method is that the new node will always be the head of the new list. The steps are as follows:

1. nextPoint to thehead.next
2. head.nextPoint to thepre(Pre’s initial value is null)
3. prePoint to thehead
4. headPoint to thenext
5. Repeat steps 1 to 4 as long as there is another node on the list

example

Assume the linked list is 1->2->3

1. nextPoint to thehead.next.nextThe pointing result is2 - > 3
2. head.nextPoint to thepreAt this time,headThe result of pointing is zero1->null
3. prePoint to theheadAt this time,preAs the result of the1->null
4. headPoint to thenext.headThe result of pointing is zero2 - > 3
5. The next node on the list, repeat step 1,nextThe pointing result is3
6. Repeat step 2,headThe result of pointing is zero2 - > 1
7. Repeat step 3,preAs the result of the2 - > 1
8. Repeat step 4,headThe result of pointing is zero3
9. . And so on. In the endpreAs the result of the3 - > 2 - > 1

Second, the implementation

Plan a

The implementation code

    /** * recursive */
    public ListNode reverseKGroup(ListNode head, int k) {
        // List is used to store the removed nodes
        List<ListNode> list = new ArrayList<>();
        ListNode headTemp = head;
        ListNode newHead = new ListNode();
        ListNode newHeadTemp = newHead;
        // Process k nodes
        for (int i=0; i<k; i++) {
            if (headTemp == null) {
                return head;
            }
            list.add(headTemp);
            headTemp = headTemp.next;
        }
        for (int i=k-1; i > -1; i--) {
            newHeadTemp.next = list.get(i);
            newHeadTemp = newHeadTemp.next;
        }
        newHeadTemp.next = reverseKGroup(headTemp, k);
        return newHead.next;
    }
Copy the code

The test code

    public static void main(String[] args) {
/ / [1, 2, 3, 4, 5]
        ListNode l = new ListNode(1.new ListNode(2.new ListNode(3.new ListNode(4.new ListNode(5)))));
        ListNode ret = new Number25().reverseKGroup(l, 2);
        System.out.println(ret);
    }
Copy the code

The results of

Plan 2 (Reverse in situ)

The implementation code

    /** * recursion * tips: Changes in place are faster */
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        / / end nodes
        ListNode tail = head;
        for (int i=0; i<k; i++) {
            if (tail == null) {
                return head;
            }
            tail = tail.next;
        }
        ListNode newHead = null;    // New header node
        ListNode next;  // Next node
        ListNode pre = head;
        while(pre ! = tail) { next = pre.next; pre.next = newHead; newHead = pre; pre = next; } head.next = reverseKGroup(tail, k);return newHead;
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥