// 要实现没k个节点进行翻转的操作,可以按照一下步骤进行 // 1.计算链表长度 // 2.分组反转 // 3. 使用一个虚拟头节点来处理边界情况 // 4.每次处理k个节点进行反转 // 5.如果剩余节点不足k个 则保持原有顺序 // 6.依次反转每组中的节点
// 1.使用prevGroupEEnd追踪上一个组的末尾 // 2.对于每个完整的k个节点组进行反转 // 3.设置groupStart为当前组的开头 // 4.nextGroupStart用于标记下一个组的起始点 // 5.反转当前组的节点,通过调整指针 // 6.将反转后的组重新链接到链表 // 7.更新preGroupEEnd为当前组的末尾
代码如下:
public class reverseGroup {public ListNode reverseKGroup(ListNode head, int k) {// 要实现没k个节点进行翻转的操作,可以按照一下步骤进行// 1.计算链表长度// 2.分组反转// 3. 使用一个虚拟头节点来处理边界情况// 4.每次处理k个节点进行反转// 5.如果剩余节点不足k个 则保持原有顺序// 6.依次反转每组中的节点// TODOif(head == null || k<=1){return head;}ListNode current = head;int count=0;while(current!=null){count++;current=current.next;}ListNode dummy = new ListNode(0);dummy.next = head;ListNode prevGroupEEnd=dummy;while(count>=k){ListNode groupStart=prevGroupEEnd.next;ListNode nextGroup=groupStart;for(int i=0;i<k;i++){nextGroup=nextGroup.next;}// 反转当前组合ListNode prev=nextGroup;current=groupStart;for(int i=0;i<k;i++){ListNode temp=current.next;current.next=prev;prev=current;current=temp;}prevGroupEEnd.next=prev;prevGroupEEnd=groupStart;count-=k;}return dummy.next;}
}
// 1.使用prevGroupEEnd追踪上一个组的末尾
// 2.对于每个完整的k个节点组进行反转
// 3.设置groupStart为当前组的开头
// 4.nextGroupStart用于标记下一个组的起始点
// 5.反转当前组的节点,通过调整指针
// 6.将反转后的组重新链接到链表
// 7.更新preGroupEEnd为当前组的末尾
如果看不懂链表翻转的过程可以看下这个博主的视频,讲的挺好的。
【小白学算法】反转链表_哔哩哔哩_bilibili