This is the seventh day of my participation in the August More text Challenge. For details, see:August is more challenging
A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast
1. The subject
I give you a list, and I flip it every k nodes, and I ask you to return the 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, leave the last remaining nodes in their original 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 a node, but actually switch nodes.
Example 1: Input: head = [1,2,3,4,5], k = 2 Output: [2,1,4, 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] Example 4: Input: head = [1], k = 1Copy the code2.
1. Invert k elements starting with head.
2. Recursively call reverseKGroup with the k + 1 element as head.
3. Connect the results of the two processes.
See the code for detailed parsing:
ListNode reverseKGroup(ListNode head, int k) { if (head == null) return null; ListNode a, b; a = b = head; for (int I = 0; I < k; I ++) { Base case if (b == null) return head; b = b.ext;} ListNode newHead = reverse(a, b); A.ext = reverseKGroup(b, k); return newHead;} */ ListNode reverse(ListNode a, ListNode b) {ListNode pre, cur, NXT; pre = null; cur = a; NXT = a; while (cur!= b) {NXT = cur. Cur = NXT;} return pre;}Copy the code
A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast