Reverse Nodes in k-Group
Description
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 题解:LeetCode-Solution