原文:25. k个一组翻转链表(leetcode 高频面试题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址:https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-025/

题目:

难度: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相连,21相连,13相连;

当反转3时,将头结点3相连,32相连,14相连。

/**
 * @来源: 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
};