题解 | #牛群的重新分组#
牛群的重新分组
https://www.nowcoder.com/practice/267c0deb9a6a41e4bdeb1b2addc64c93
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ public ListNode reverseKGroup (ListNode head, int k) { if(head==null){ return null; } // 通过函数计算链表长度 int length=getLength(head); // 判断链表是否小于k,小于k不需要进行翻转 if(length<k){ return head; } // 否则声明指针用于记录翻转过程 ListNode pre=null; ListNode cur=head; // 声明一个计数器 int index=0; // 翻转前k个节点 while(index<k){ ListNode next=cur.next; cur.next=pre; pre=cur; cur=next; index++; } //递归翻转剩余节点 head.next=reverseKGroup(cur,k); return pre; } private int getLength(ListNode head){ int length=0; while(head!=null){ length++; head=head.next; } return length; } }
解题语言:java
本题的知识点:链表的翻转,递归,链表的遍历
思路如下:
首先,判断给定的链表是否为空。如果为空,直接返回null。
接下来,计算链表的长度。使用一个辅助函数getLength(),通过遍历链表来统计节点的数量。
然后,判断链表的长度是否小于k。如果小于k,说明不需要进行翻转,直接返回头节点head。
否则,声明一个指针pre和cur,用于记录翻转的过程。初始化pre为null,cur为头节点head。同时,声明一个计数器index,初始值为0。
在while循环中,翻转前k个节点。每次循环中,将cur指向的节点的下一个节点保存为next,然后将cur指向的节点的next指向pre,更新pre为cur,cur为next,计数器index自增1。
当翻转结束后,head指向当前翻转的链表段的尾节点,pre指向当前翻转的链表段的头节点。将head.next指向递归调用reverseKGroup()返回的结果,即翻转剩余部分链表,并将翻转后的链表段的头节点pre返回。
最后,返回pre,即整个链表翻转后的结果。
整体思路就是利用递归和迭代的方式,先翻转前k个节点,然后递归处理剩余的节点,再将各个翻转后的链表段连接起来。这样就实现了将链表按照每k个节点进行翻转的功能。
时间复杂度分析:
遍历一次链表来计算链表的长度的时间复杂度为O(n),其中n是链表的长度。
翻转过程中需要遍历k个节点,所以时间复杂度为O(k)。
递归调用reverseKGroup函数的次数最多为n/k次,其中n/k是链表的长度除以k的整数部分。
整体的时间复杂度为O(n),具有很好的时间效率。