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

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

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

Note:

• Only constant extra memory is allowed.
• You may not alter the values in the list's nodes, only nodes itself may be changed.

Tags: Linked List

题意是让你以 k 个元素为一组来翻转链表，最后不足 k 个的话不需要翻转，最传统的思路就是每遇到 k 个元素，对其 k 个元素进行翻转，而难点就是在此，下面介绍其原理，我们以例子中的 k = 3 为例，其 pre 和 next 如下所示。

0->1->2->3->4->5 | | pre next 

我们要做的就是把 pre 和 next 之间的元素逆序，思想是依次从第二个元素到第 k 个元素，依次把它插入到 pre 后面，过程如下。

 head move | | 0->1->2->3->4->5 | | pre next head move | | 0->2->1->3->4->5 | | pre next head move | | 0->3->2->1->4->5 | | pre next 

好了，根据原理，那写出代码就不难了。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */classSolution { publicListNodereverseKGroup(ListNodehead, intk) { if (head == null || k == 1) returnhead; ListNodenode = newListNode(0), pre = node; node.next = head; for (inti = 1; head != null; ++i) { if (i % k == 0) { pre = reverse(pre, head.next); head = pre.next; } else { head = head.next; } } returnnode.next; } privateListNodereverse(ListNodepre, ListNodenext) { ListNodehead = pre.next; ListNodemove = head.next; while (move != next) { head.next = move.next; move.next = pre.next; pre.next = move; move = head.next; } returnhead; } }

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：awesome-java-leetcode