学步园

题目：

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

思路：

本题没有什么算法点。需要注意的就是在一边遍历的时候要一边把前一个记录下来（为pre），然后把当前节点（cur）的next连接到pre，同时，要掌握原有顺序

中的cur的next是那个节点（为pro），之后cur=pro，再次进入reverse流程。

其中要注意的两点：刚开始的时候，cur=head，此时pre=null；需要特殊处理

                                最后的节点是新的连接的头。

易错点：上述思路仅仅是一个k的长度内的倒置。k外面还会有一个按照最初顺序遍历的指针，当k中 的倒置好之后，外面的指针不能再按照原来的变量进行next计算，因为

那些变量的next都已经在k长度的倒置过程中改变了。因此需要事先记录接缝处的变量，然后再倒置中间的k个节点。

注意：边界条件：如果k>list.lengh 或 k<=1，则依然是原来顺序。

AC代码：

private void reverse(ListNode pre, ListNode head, ListNode end) {
        ListNode p = pre;
        ListNode cur = head;
        while (cur != end) {
            ListNode tmp = cur.next;
            if (cur == head)
                cur.next = end.next;
            else
                cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        cur.next = pre;
        if (p != null)
            p.next = cur;
    }

    private ListNode searchHead(ListNode head, int k) {
        int count = 0;
        ListNode cur = head;
        while (cur != null && count < k) {
            count++;
            if (count == k)
                return cur;
            cur = cur.next;
        }
        return head;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if(k<=1)
            return head;
        ListNode newHead = searchHead(head, k);
        if (newHead == head)
            return newHead;

        int count = 0;
        ListNode cur = head;
        ListNode curHead = head;
        ListNode preHead = null;
        while (cur!=null) {
            count++;
            if (count == k) {
                ListNode nextBegin = cur.next;
                reverse(preHead, curHead, cur);
                cur = nextBegin;
                preHead = curHead;
                count = 0;
            } else {
                if (count == 1)
                    curHead = cur;
                cur = cur.next;
            }
        }
        return newHead;
    }