假设当前需要反转的子链表为[curHead, curTail]
curDummy：当前需要反转的子链表的虚拟节点
curHead：当前需要反转的子链表的头节点
curTail：当前需要反转的子链表的尾节点
- 找到尾节点curTail
- 反转子链表[curHead, curTail]（反转子链表解法参考反转子链表题解2）
- 更新curDummy、curHead
- 重复1、2、3步，直至尾节点curTail为null（子链表不满足长度），头节点curHead为null（已经反转完所有的子链表）
题解1
小细节：反转子链表时，如果head==tail，子链表长度为1时，记得将子链表与原链表断开，否则 while(curDummy.next != null)会死循环。
反转子链表——递归代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0, head);
ListNode curHead = head, curTail = head, curDummy = dummy;
while(curHead != null) {
curTail = cut(curHead, k);
if(curTail == null) {
curDummy.next = curHead;
break;
}
ListNode next = curTail.next;
curDummy.next = reverse(curHead, curTail);
while(curDummy.next != null) curDummy = curDummy.next;
curHead = next;
}
return dummy.next;
}
public ListNode cut(ListNode head, int len) { // 返回尾节点
ListNode tail = head;
-- len;
while(tail != null && len -- > 0) {
tail = tail.next;
}
if(len > 0) return null;
return tail;
}
public ListNode reverse(ListNode head, ListNode tail) {
if(head == tail) {
head.next = null;
return head;
}
ListNode res = reverse(head.next, tail);
head.next.next = head;
head.next = null;
return res;
}
}
题解2
小细节：该种解法没有断开子链表，因此 while(curDummy.next != next)循环直至子链表的下一个节点结束。
反转子链表——空间复杂度O(1)代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0, head);
ListNode curDummy = dummy, curHead = head, curTail;
while(curHead != null) {
curTail = findTail(curHead, k);
if(curTail == null) {
curDummy.next = curHead;
break;
}
ListNode next = curTail.next;
curDummy.next = reverse(curDummy, curHead, curTail, next);
while(curDummy.next != next) curDummy = curDummy.next;
curHead = next;
}
return dummy.next;
}
public ListNode findTail(ListNode head, int len) {
-- len;
while(head != null && len -- > 0) {
head = head.next;
}
if(len > 0) return null; // 此时子链表不满足长度len
return head;
}
public ListNode reverse(ListNode dummy, ListNode head, ListNode tail, ListNode next) {
ListNode suc = head.next;
while(suc != next) {
head.next = suc.next;
suc.next = dummy.next;
dummy.next = suc;
if(head != next) suc = head.next;
}
return dummy.next;
}
}