题目:
难度:Hard
相关话题:链表
给出一个链表,每k 个节点一组进行翻转,并返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是k 的整数倍,那么将最后剩余节点保持原有顺序。
示例 :
给定这个链表: 1->2->3->4->5
当k = 2 时,应当返回: 2->1->4->3->5
当k = 3 时,应当返回: 3->2->1->4->5
说明 :
思路:
相当于重复多个链表的部分转换,参考NO.92
。
首先计算出原链表head
的长度,计算出反转k
个节点,能执行几次反转。
反转链表需要一个一个节点来处理。
例如 [1->2->3->4->5],k=3
反转从第1
个节点开始,我们首先要找到头部节点(一个空的新节点),因为后续所有的反转都是在头部节点的next
上处理的。
同时,我们需要找到一个尾巴节点,例如反转3
的时候,节点1
就是尾巴节点,它的作用就是将要反转的3
后面的节点连接起来。
这两个节点头部节点(空)
和尾巴节点(1)
是不变的。
当反转2
时,将头结点
和2
相连,2
和1
相连,1
和3
相连;
当反转3
时,将头结点
和3
相连,3
和2
相连,1
和4
相连。
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function(head, k) {
if(!head)return null
let len=0,node=head
while(node){
node=node.next
len++
}
let root=new ListNode(null)
root.next=head
let startNode=root,tailNode=startNode.next
node=root.next
let t=Math.floor(len/k)
while(t-->0){
let n=k
node=node.next
while(n-->1){
let secondNode=startNode.next
let nxt=node.next
startNode.next=node
node.next=secondNode
tailNode.next=nxt
node=nxt
}
startNode=tailNode
tailNode=startNode.next
}
return root.next
};