leetcode第25题（困难）

原链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

问题描述

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

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

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

示例：

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

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

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

解题思路

整体思路是将原链表分成p（p=n个节点 / k）段（逻辑上的分），每段都有一个头节点和一个尾节点。

第一步先遍历一次整个原链表，当每一组节点满足有k个节点时，标记当前组的头节点和尾节点。

第二步翻转链表，改变每组的头节点和尾节点的引用。返回第一组的头节点即可。

这样的时间复杂度就是 O(n)+O(n/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) {
        return begin(head,k);
    }
    public static ListNode th;

    /**
     *  拼接反转的链表
     * @param listNode
     * @param k
     * @return
     */
    public static ListNode begin(ListNode listNode,int k){
        if(k==1){
            return listNode;
        }
        th=listNode;
        LinkedList<HeadTail> ov=new LinkedList();
        while(th!=null){
            ListNode head=th;
            ListNode tail=reversal(th,k);
            ov.addLast(new HeadTail(tail,head));
        }
        if(ov.size()==0){
            return null;
        }else{
            HeadTail headTail=ov.removeFirst();
            ListNode head=headTail.head;
            ListNode tail=headTail.tail;
            while(ov.size()>0){
                headTail=ov.removeFirst();
                tail.next=headTail.head;
                tail=headTail.tail;
            }
            return head;
        }
    }

    /**
     *  反转链表
     * @param node
     * @param k
     * @return
     */
    public static ListNode reversal(ListNode node,int k){
        ListNode p=null;
        ListNode n;
        int i=0;
        while(node.next!=null){
            n=node.next;
            node.next=p;
            p=node;
            node=n;
            i++;
            if(i==k-1){
                break;
            }
        }
        th=node.next;
        node.next=p;
        if(i<k-1){
            node=reversal2(node,k);
        }
        return node;
    }

    /**
     *  反转链表
     * @param node
     * @param k
     * @return
     */
    public static ListNode reversal2(ListNode node,int k){
        ListNode p=null;
        ListNode n;
        while(node.next!=null){
            n=node.next;
            node.next=p;
            p=node;
            node=n;
        }
        node.next=p;
        return node;
    }
    public static class HeadTail {
        ListNode head;
        ListNode tail;
        public HeadTail(ListNode head,ListNode tail){
            this.head=head;
            this.tail=tail;
        }
    }
}