25. Reverse Nodes in k-Group 发表于 2021-12-18 Recursion1234567891011121314151617181920212223242526272829303132class Solution { public ListNode reverseKGroup(ListNode head, int k) { // 1 2 3 4 5, when k == 3 ListNode curr = head; for (int i = 0; i < k - 1 && curr != null; i++) { curr = curr.next; } if (curr == null) { // 不足 k 个无需翻转,curr 停留在第 k 个节点上 return head; } ListNode nextHead = curr.next; curr.next = null; ListNode newHead = reverse(head); head.next = reverseKGroup(nextHead, k); return newHead; } private ListNode reverse(ListNode head) { ListNode pre = null, curr = head; while (curr != null) { ListNode next = curr.next; curr.next = pre; pre = curr; curr = next; } return pre; }} Iterate12345678910111213141516171819202122232425262728293031323334353637383940414243444546class Solution { public ListNode reverseKGroup(ListNode head, int k) { // d 1 2 3 4 5, when k == 3 ListNode dummyHead = new ListNode(-1, head); ListNode pre = dummyHead; while (pre.next != null) { ListNode currHead = pre.next; ListNode curr = currHead; for (int i = 0; i < k - 1 && curr != null; i++) { curr = curr.next; } if (curr == null) { // 不足 k 个,直接返回 break; } ListNode nextHead = curr.next; curr.next = null; ListNode reversedHead = reverse(currHead); // d 3 2 1 4 5 // r ch pre.next = reversedHead; currHead.next = nextHead; pre = currHead; } return dummyHead.next; } private ListNode reverse(ListNode head) { ListNode pre = null, curr = head; while (curr != null) { ListNode next = curr.next; curr.next = pre; pre = curr; curr = next; } return pre; }} Reference25. Reverse Nodes in k-Group