If the number of nodes in the linked list is not a multiple of K, leave the last remaining nodes as they are. You can’t change the value in the node, only the node itself. Ask for space complexity O(1) For example: Given a linked list of 1→2→3→4→5 for k=2 you should return 2→1→4→5 for k=3 you should return 3→2→1→4→5

Solution 1: The easiest way to do this is to group linked lists of K items, then reverse them individually, and then join them together.Copy the code

Solution: Group reverse connection

import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; *} */ public class Solution {/** ** @param head ListNode * @param k int * @return ListNode */ public ListNode ReverseKGroup (ListNode head, int k) {dummy = new ListNode(0); dummy.next=head; ListNode pre = dummy; ListNode pre = dummy; ListNode pre = dummy; ListNode end = dummy; while(end.next! For (int I =0; for(int I =0; i<k; i++){ end=end.next; } if(end==null) break; ListNode start =pre.next; ListNode start =pre.next; ListNode start =pre.next; // List next =end.next; End. Next =null; // Get [start, end] off the list. // There is a big reverseNode. // After the inversion,start reverses to the end of the list and connects to the head node of the next inversion. pre=start; end=start; } return dummy; } public ListNode reverse(ListNode head){ListNode pre=null; ListNode temp=null; while(head! =null){ temp=head.next; head.next=pre; pre=head; head=temp; } return pre; }}Copy the code
1. Find k nodes to be flipped first. If the remaining nodes are smaller than K, there is no need to flip, and just return to the head node directly. The k nodes are flipped and the flipped head node is returned, that is, the tail node after this operation is the head node of the next operation (flipped to the left closed and right open range). 3. Recursively flip k nodes 4. Point the tail node after the last flip to the head node after the next flip, which is the connection operation.Copy the code

Solution two: recursive implementation

import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; *} */ public class Solution {/** ** @param head ListNode * @param k int * @return ListNode */ public ListNode reverseKGroup (ListNode head, int k) { if(head==null||head.next==null){ return head; } ListNode tail=head; for(int i=0; i<k; If (tail==null){return tail; } tail=tail.next; ListNode res=reverseNode(head,tail); // There is a tail head. Next =reversKGroup(tail,k) return res; } /** * flip the list * tail is critical * @param head ListNode class * @param tail ListNode * @return ListNode class */ public ListNode reverseNode(ListNode head,ListNode tail){ ListNode pre=null; ListNode next=null; while(head! =tail){ next=head.next; head.next=pre; pre=head; head=next; } return pre; }}Copy the code
According to the FILO feature of the stack, the flip effect can be achieved in the process of loading and unloading the stack at one time. Note the k constraint, if there are less than k elements in the stack there is no need to flip. 2. The part that has been flipped (off the stack) is connected to the rest.Copy the code

Solution 3: through the stack implementation

import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; *} */ public class Solution {/** ** @param head ListNode * @param k int * @return ListNode */ public ListNode ReverseKGroup (ListNode head, int k) {Stack<ListNode> Stack = new Stack<ListNode>(); ListNode res = new ListNode(0); // Define a pointer to the new list to prevent subsequent operations from changing the head node ListNode p = res; ListNode temp =head; ListNode temp =head; ListNode temp =head; int count =0; // loop in while(tem! =null&&count<k){ stack.push(temp); temp=temp.next; count++ } if(count! If (p < 0, p < 0, p < 0); } // exit the stack while(! stack.isEmpty()){ p.next=stack.pop(); p=p.next; } // reset the initial node for the next operation. head=temp; } return res.next; }}Copy the code