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.
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
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; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k == 1) return head;
ListNode node = new ListNode(0), pre = node;
node.next = head;
for (int i = 1; head != null; ++i) {
if (i % k == 0) {
pre = reverse(pre, head.next);
head = pre.next;
} else {
head = head.next;
}
}
return node.next;
}
private ListNode reverse(ListNode pre, ListNode next) {
ListNode head = pre.next;
ListNode move = head.next;
while (move != next) {
head.next = move.next;
move.next = pre.next;
pre.next = move;
move = head.next;
}
return head;
}
}如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：awesome-java-leetcode