题目描述
给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
代码
/**
* 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(-1, head);
ListNode pre = dummy, cur = head;
while(cur!=null){
ListNode p = pre;
for(int i=0; i<k; i++){
p = p.next;
if(p==null) return dummy.next;
}
ListNode nex = p.next; //预先存储下一个节点
ListNode[] a = reverse(cur, p); //翻转
pre.next = a[0]; a[1].next = nex; //将子链表嵌入总链表
pre = a[1]; cur = nex;
}
return dummy.next;
}
//将k个节点进行翻转,每次只将节点pre与节点cur之间的边翻转
public ListNode[] reverse(ListNode head, ListNode tail){
ListNode pre = tail.next, cur = head;
while(pre!=tail){
ListNode nex = cur.next;
cur.next = pre;
pre = cur;
cur = nex;
}
return new ListNode[]{tail, head};
}
}