25. K 个一组翻转链表

题意：

图示：

递归图示：

解题思路：

思路：
    1. for 循环找到第k个节点
    2. 从头到k个节点，进行反转，并返回翻转后的头结点newnode
    3. 继续对下一轮k个节点反转；
    5. 将上一轮反转后的尾节点，指向下一轮反转的头节点，确保每一轮反转后节点相连；
    6. 最后返回newnode头节点

PHP代码实现：

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {
    function reverseKGroup($head, $k) {
        $node = $head;
        for ($i = 0; $i < $k; $i++) {
            if (!$node) return $head;
            $node = $node->next;
        }
        $newHead = $this->reverse($head, $node);
        $head->next = $this->reverseKGroup($node, $k);
        return $newHead;
    }
    function reverse($start, $end) {
        $pre = null;
        while ($start != $end) {
            $next = $start->next;
            $start->next = $pre;
            $pre = $start;
            $start = $next;
        }
        return $pre;
    }
}

GO代码实现：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    node := head
    for i := 0; i < k; i++ {
        if node == nil { return head } 
        node = node.Next
    }
    newHead := reverse(head, node)
    head.Next = reverseKGroup(node, k)
    return newHead
}
func reverse(head, tail *ListNode) *ListNode {
    p, q := head, head.Next
    p.Next = tail
    for q != tail {
        r := q.Next
        q.Next = p
        p = q
        q = r
    }
    return p
}