Leetcode-25. K 个一组翻转链表

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

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

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

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

运行结果

解题思路
正常的迭代是从头到尾反转，也就是从head到null。我们将null改成节点b就是从head到b
之后利用递归+迭代，实现k个反转，再和后续的节点连接在一起
java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null) return null;
        ListNode a,b;
        a=b=head;
        for(int i=0;i<k;i++){
            if(b==null) return head;
            b=b.next;
        }//从头开始，a为头，b为第k个。反转[a,b)
        ListNode newhead=reverse(a,b);//首次反转的头结点就是最后返回的头结点
        a.next=reverseKGroup(b,k);//a为尾结点，连接后半段返回的头结点
        return newhead;

    }
    public ListNode reverse(ListNode a,ListNode b){
        ListNode pre,cur,nxt;
        pre=null;
        cur = a;
        nxt = a;
        while(cur != b){//将null改成b就是反转a到b
            nxt=cur.next;
            cur.next=pre;
            pre=cur;
            cur=nxt;
        }
        return pre;
    }
}