<?php

class ListNode {

public $val = 0;

public $next = null;

function __construct($val = 0, $next = null) {

$this->val = $val;

$this->next = $next;

}

}

/**

* @param ListNode $head

* @param Integer $k

* @return ListNode

*/

function reverseKGroup($head, $k)

{

if ($head === null) {

return null;

}

if ($k === 1) {

return $head;

}

//虚拟头节点

$dummyHead = new ListNode();

//尾指针节点

$tail = $dummyHead;

$curNode = $head;

while ($curNode !== null){

$i = 0;

$p = $curNode;

while ($p !== null){

$i++;

if($i == $k){

break;

}

$p = $p->next;

}

if($p === null){

$tail->next = $curNode;

return $dummyHead->next;

}else{

$tmp = $p->next;

list($tail->next, $tail) = getReverseNodeList($curNode, $p);

$curNode = $tmp;

}

}

return $dummyHead->next;

}

function getReverseNodeList($head, $tail)

{

$prev = null;

$cur = $head;

while ($cur !== $tail){

$next = $cur->next;

$cur->next = $prev;

$prev = $cur;

$cur = $next;

}

//原尾部转为头部，头部转为尾部

$tail->next = $prev;

// $prev = $tail;

return [$tail, $head];

}