Reverse the head list as group M: Example: Suppose m=3. List 1 - > 2 - > 3 - > 4 - > 5 - > 6-7-8 output > > : 3 - > 2 - > 1 - > 6 - > 5 - > 4-7 - > > 8Copy the code

You can solve this problem by using the stack structure. If the value in the stack is K, the stack will be ejected

Use stack structure, time complexity O(n), control complexity O(K)

1. The code is as follows:

1.1 the Node. Java

package com.yuhl.right.node;

/ * * *@author yuhl
 * @Date 2020/10/24 15:36
 * @Classname Node
 * @Description TODO
 */
public class Node {
    private int value;
    private Node next;

    public Node(a) {}public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }

    public int getValue(a) {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getNext(a) {
        return next;
    }

    public void setNext(Node next) {
        this.next = next; }}Copy the code

1.1 NoteTest. Java

package com.yuhl.right.node;

import com.yuhl.Main;

import java.util.Stack;

/ * * *@author yuhl
 * @Date2020/10/24 insisting *@Classname NoteTest
 * @Description* * Reverse the head singly linked list as group m (not if it is less than m) : * Example: Assume m=3. List 1 - > 2 - > 3 - > 4 - > 5 - > 6-7-8 * > > output: 3 - > 2 - > 1 - > 6 - > 5 - > 4-7-8 * / > >
public class NoteTest {
    public static void main(String[] args) {
        // Build a singly linked list
        Node node8 = new Node(8.null);
        Node node7 = new Node(7, node8);
        Node node6 = new Node(6, node7);
        Node node5 = new Node(5, node6);
        Node node4 = new Node(4, node5);
        Node node3 = new Node(3, node4);
        Node node2 = new Node(2, node3);
        Node node1 = new Node(1, node2);
        Node nodeRev = getRevNode(node1,3);// Get the rotated list
        printLinck(nodeRev, 8);// Prints the rotated list
    }

    /** * use stack structure, time complexity O(n), control complexity O(K) *@paramHead Specifies the header *@paramK is a group of K *@returnNew header * */
    private static Node getRevNode(Node head, int K) {
        if (K < 2) {// Return the current header if there is only one
            return head;
        }

        // hold K nodes in stack
        Stack<Node> stack = new Stack<>();
        Node newHead = head;// New header, return value used
        int count = 1;// count, reset to 1 for each K
        Node cur = head;// The current node
        Node pre = null;// The previous node
        Node next = null;// The last node
        while(cur ! =null) {
            next = cur.getNext();
            stack.push(cur);
            if (stack.size() == K) {
                pre = pesign1(stack, pre, next);
                newHead = newHead == head ? cur : newHead;// If newHead == head, fetch a cur node, or fetch newHead, the assignment has already been done.
            }
            cur = next;
        }
        return newHead;
    }

    private static Node pesign1(Stack<Node> stack, Node left, Node right) {
        Node cur = stack .pop();
        if(left ! =null) {
            left.setNext(cur);
        }
        Node next = null;
        while(! stack.isEmpty()) { next = stack.pop(); cur.setNext(next); cur = next; } cur.setNext(right);return cur;

    }

    private static void printLinck(Node nodeRev, int len) {
        Node noteTem = nodeRev;
        for (int i = 0; i < len; i++) {
            if (i == len - 1) {// the last node does not need to be followed ->
                System.out.print(noteTem.getValue());
            } else {
                System.out.print(noteTem.getValue() + "- >"); } noteTem = noteTem.getNext(); }}}Copy the code

2. The running result is as follows:

"C: \ Program Files \ Java \ jdk1.8.0 _201 \ bin \ Java exe"
3->2->1->6->5->4->7->8
Copy the code

3. The running results are as follows:

Easier to understand ways to write code:

3.1 the Node. Java

package com.yuhl.test001.revNode;

/ * * *@author yuhl
 * @Date* loathsome 2020/10/31@Classname Node
 * @DescriptionLinked list optional Node class */
public class Node {
    public int value;
    public Node next;

    public Node(a) {}public Node(int value, Node next) {
        this.value = value;
        this.next = next; }}Copy the code

3.2 RevNodeTest. Java

package com.yuhl.test001.revNode;

import com.yuhl.right.tree1.TreeNodeTest2;

import java.util.Stack;

/ * * *@author yuhl
 * @Date2020/10/31 but *@Classname RevNodeTest
 * @DescriptionAlgorithm 002: Reverse the order between each K nodes of a single linked list. Example: Suppose m=3. List 1 - > 2 - > 3 - > 4 - > 5 - > 6 - > 7 - > 8 Output: 3 - > 2 - > 1 - > 6 -. * /
public class RevNodeTest {
    public static void main(String[] args) {
        // Build a singly linked list
        Node node8 = new Node(8.null);
        Node node7 = new Node(7, node8);
        Node node6 = new Node(6, node7);
        Node node5 = new Node(5, node6);
        Node node4 = new Node(4, node5);
        Node node3 = new Node(3, node4);
        Node node2 = new Node(2, node3);
        Node head = new Node(1, node2);
        Node newHead = revNode(head, 4);
        printnewHead(newHead);
    }

    // Print the linked list
    private static void printnewHead(Node newHead) {
        Node tmpNode = newHead;
        while (true) {
            if(tmpNode ! =null) {
                System.out.print(tmpNode.value+ "");
                if(tmpNode.next ! =null) {
                    tmpNode = tmpNode.next;
                } else {
                    break; }}}}public static Node revNode(Node head,int len){
        if (head.next == null || len <= 1) {// If there is only one node, return it directly
            return head;
        }
        Node newHead = null;// Return the head of the new list
        Node curNode = head;// Temporary node, used for pushing
        Node tmpNode = null;// Temporary node: used out of the stack
        Node preNode = null;// The last of N nodes, used to connect N+1 nodes forward
        Node noRevNode = null;// Record the first item in each stack.
        Node preNodeSer = null;// The front node when the stack is ejected
        / / into the stack
        Stack<Node> stack = new Stack();
        int flag = 1;// 1: can be rotated, 0: can not be rotated, less than len
        while(flag == 1) {/ / into the stack
            for (int i = 1; i <= len; i++) {
                if(i == 1){
                    noRevNode = curNode;
                }
                stack.push(curNode);
                if(curNode.next ! =null) {
                    curNode = curNode.next;
                } else {
                    // connect the last node of n to the current node.
                    flag = 0; // Can rotate,
                    break;// No rotation if len is insufficient}}/ / out of the stack
            if (stack.size() == len) { / / rotation
                for (int i = 1; i <= len; i++) {
                    Node popNode = stack.pop();
                    tmpNode = popNode;

                    if (newHead == null) {// The first popup is the new first node, otherwise the first node is already occupied, indicating >1 popup
                        newHead = popNode;
                        preNodeSer = popNode;
                    } else {
                        preNodeSer.next = tmpNode;
                        preNodeSer = tmpNode;
                        if(i == len){// Record the last node to be connected to the next node
                            preNode = popNode;// preNode = tmpNode;
                            if (0 == flag) {
                                preNode.next = null;// Otherwise it will print circularly
                            }
                        }
                    }
                }
            } else {/ / not rotating
                if (newHead == null) {// if len>size
                    return head;
                }
                preNode.next = noRevNode;
            }

            if (tmpNode.next == null) {
                flag = 0; }}returnnewHead; }}Copy the code

3.3 Running Results

4, 3, 2, 1, 8, 7, 6, 5Copy the code