- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
递归
1.通过 k 来确定翻转链表的范围，进行翻转并返回翻转后的头节点。
2.记得处理边界条件，不要陷入人肉递归。
3.递归链接后续 k 个翻转的链表头节点，将上一轮翻转后的尾节点指向下一轮翻转后的头节点。
constreverseKGroup=function(head,k){if(head===null){returnnull}letstart=headletend=headfor(leti=0;i<k;i++){if(end===null){returnstart}end=end.next}// 翻转前 k 个letnewHead=reverse(start,end)// 递归翻转后面的链表并进行链接start.next=reverseKGroup(end,k)returnnewHead}constreverse=function(head,tail){letprev=nullletcurr=headwhile(curr!==null){// 记录 next 节点letnext=curr.next// 反转指针curr.next=prev// 推进指针prev=currcurr=next}// 返回翻转后的头节点returnprev}
- 时间复杂度：O(n)
- 空间复杂度：O(1)