leetCode算法题-----25 : K 个一组翻转链表_PHP

取自leetCode算法题第25道

1.链接: https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
2. 题目描述

A. 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。


    k 是一个正整数，它的值小于或等于链表的长度。


    如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。


B.
示例 1
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
示例 2
输入：head = [1,2,3,4,], k = 2
输出：[2,1,4,3]

3.题解 :

let list2 = {
    data : 1,
    next : {
        data : 3,
        next : {
            data : 4,
            next : {
              data : 6,
              next : {
                  data :9,
                  next:{
                    data :10,
                    next : {
                        data:11,
                        next:{
                            data:12,
                            next:null
                        }
                    } 
                  }
              }
            }
        }
    }
}
// 返回链表的长度
function listSize(list){
     let index = 0
    while(list){
        index ++
        list = list.next
    }
    return index
}
// 反转指定长度的链表 k长度
function reverse(list,k){     
    let current = null
    let next = null
    let index = 0
    let end = list
    let oldnext = null // 长度不够不需要翻转 用于保存老的链表的指针
    while(list){
        index ++
        next = list.next
        list.next = current
        current = list
        list = next
        if(index == k){
            // 长度够了
              break;
        }
    }
    return {current,next,end} // current相当于链表的第一个数据域   next 下一次要反转的开始 当前翻转完成链表的最后一个数据域
}

function reverseKGroup(list,k){
let current = null
let end = null
  while(list){ // 这一个while循环是 n/k 次
    //   debugger
    if(listSize(list) >= k){ // 如果链表的长度大于等于指定 长度 则需要翻转 否则不需要翻转 
        let res  = reverse(list,k) // 循环k次
        list = res.next      // 下一次要翻转的链表
       if(end) end.next = res.current
        end = res.end // 每次翻转之后的尾
        if(!current)  current = res.current  // 存第一个翻转之后的头 
    }else{
        // 当前的list是 不需要翻转的list
        end.next = list
        break
    }
  }
  return current
}
console.log(reverseKGroup(list2,3))