思路:
首先知道如何反转链表,其次找出每组的开始节点和结束节点,然后对于不足与k个的链表保持原状。
代码如下:
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head==null||k==1){
return head;
}
ListNode start=head;
//获取k个一组的尾节点
ListNode end=getKGroupEnd(start,k);
if (end==null){
return head;
}
//记录头节点 反正后end 就是头节点
head=end;
//反转第一组
reverse(start,end);
//上一组的尾节点
ListNode lastNode=start;
while (lastNode!=null){
start=lastNode.next;
end = getKGroupEnd(start, k);
//不够k个
if (end==null){
return head;
}
//反转
reverse(start,end);
//上一组的尾节点next指向end
lastNode.next=end;
//上一组的尾节点来到反转后的尾节点
lastNode=start;
}
return head;
}
public static void reverse(ListNode start,ListNode end){
//记录尾节点下一个位置 方便反转之后连接
end=end.next;
ListNode pre=null;
ListNode cur=start;
ListNode next;
while (cur!=end){
next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
start.next=end;
}
private ListNode getKGroupEnd(ListNode start, int k) {
ListNode end=start;
for (int i = 1; i <k&&end!=null; i++) {
end=end.next;
}
return end;
}
}