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