ReverseNodesInKGroups [source code]
public class ReverseNodesInKGroups {
static
/******************************************************************************/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (k == 1 || head == null)
return head;
ListNode dummy = new ListNode (0), cur = head, prev = dummy;
dummy.next = head;
while (cur != null) {
invert (cur, prev, k);
// advance
prev = cur;
cur = cur.next;
}
return dummy.next;
}
void invert (ListNode head, ListNode parent, int k) {
ListNode cur = head, prev = null;
for (int i = 0; i < k; i++) {
if (cur == null) {
invert (prev, parent, i); // pass I rather than I + 1: use example to see why
return;
}
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
parent.next = prev;
head.next = cur;
}
}
/******************************************************************************/
public static void main(String[] args) {
ReverseNodesInKGroups.Solution tester = new ReverseNodesInKGroups.Solution();
int[][] inputs = {
{1,2,3,4,5}, {2}, {2,1,4,3,5},
{1,2,3,4,5}, {3}, {3,2,1,4,5},
{1,2,3,4,5,6,7}, {3}, {3,2,1,6,5,4,7},
{}, {1}, {},
{}, {2}, {},
};
for (int i = 0; i < inputs.length / 3; i++) {
ListNode head = ListNode.buildListNode (inputs[3 * i]), ans = ListNode.buildListNode (inputs[3 * i + 2]);
int k = inputs[3 * i + 1][0];
System.out.println (Printer.separator ());
String head_str = ListNode.serialize (head), ans_str = ListNode. serialize (ans), output_str = ListNode.serialize (tester.reverseKGroup (head, k));
System.out.printf ("%s and %d -> %s, expected: %s\n",
head_str, k, Printer.wrapColor (output_str, output_str.equals (ans_str) ? "green" : "red"), ans_str
);
}
}
}
感觉就是前面做的几题的拓展, 难度应该是在实现上面;
最后还是做完了, 不过超时间了. 速度是12ms (5%), 不算特别好; 总体思路其实还是跟之前类似的, 通过一个等距的快慢指针的维护来完成一个一段一段的invert就行了; 这里的invert有讲究, 不是直接原来的那个套过来就能用了:
- 要传一个额外的node进去, 作为新的tail, 这个就跟我OS VM的时候的
frame_get_page的实现方式一样, 传一个额外参数比事后单独进行数据关联要方便的多; - 看这个循环, 这里这个循环不能跟平常一样直接用一个not Null来判断, 因为我们并不是一直要invert到最后, 而是用一个长度来控制;
整个算法的过程中要注意各种index数字的计算; 就从给的三个例子出发, 动笔使劲画, 整个题目本身其实并不是很难;
special case: trivial but critical
这个题目还体现一个重要问题, 最后两个case, 其实就是程序第一行的那个special case给解决掉的; 如果没有被这样的test给break掉, 你多半会觉得这种东西很trivial, 然后LeetCode的题目就是这么个套路, 就是会用这么无聊的方式去break掉你的代码. 养成上来就判断special case的好习惯, 对你没坏处. 就算最后写出来一个实际上可以自动handle special case的算法, 也不用管, 到时候在删掉就行了, 不要有Premature Optmization的思路在脑子里. 要知道, 你错过了一个test, 就算是你的代码有bug, 最后就可以决定你不被hire.
另外这几个题目都是直接用的while true + break的方法写的, 简单暴力, 写起来很轻松, 何乐而不为.
看了几个discussion之后, 感觉好像fast不是必要的; 当然, 在这里先用有fast的方式来思考是很好的, 所以我还是把有fast的版本摆在这里, 这个写起来很方便:
不对, 尝试了之后好像不行, 这个window的末尾一定要知道, 不然很麻烦; 不对, 看下面discussion部分, 最后还是相处办法来了;
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (k == 1 || head == null)
return head;
ListNode dummy = new ListNode (0), slow = head, fast = head, prev = dummy;
dummy.next = head;
for (int i = 1; i < k; i++) if ((fast = fast.next) == null)
return head;
search : while (true) {
prev.next = fast;
invert (slow, fast.next, k);
// advance
prev = slow;
if ((slow = slow.next) == null)
break search;
fast = slow;
for (int i = 1; i < k; i++) if ((fast = fast.next) == null)
break search;
}
return dummy.next;
}
// think about:
// <-(prev) (cur)->()->()->
// @HEAD: head of the list
// @NEW_TAIL: the new tail node of the inverted list
// @K: controls that the invertion only affests K nodes
void invert (ListNode head, ListNode new_tail, int k) {
ListNode cur = head, prev = new_tail;
for (int i = 0; i < k; i++) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
}
}
没有editorial;
discussion最优解用的recursion来写的:
@shpolsky said in Short but recursive Java code with comments:
Hi, guys!
Despite the fact that the approach is recursive, the code is less than 20 lines. :)
public ListNode reverseKGroup(ListNode head, int k) {
ListNode curr = head;
int count = 0;
while (curr != null && count != k) { // find the k+1 node
curr = curr.next;
count++;
}
if (count == k) { // if k+1 node is found
curr = reverseKGroup(curr, k); // reverse list with k+1 node as head
// head - head-pointer to direct part,
// curr - head-pointer to reversed part;
while (count-- > 0) { // reverse current k-group:
ListNode tmp = head.next; // tmp - next head in direct part
head.next = curr; // preappending "direct" head to the reversed list
curr = head; // move head of reversed part to a new node
head = tmp; // move "direct" head to the next node in direct part
}
head = curr;
}
return head;
}
Hope it helps!
整个算法不难理解, 还是LinkedList题目, 还是用peel head recursion来写; 你只要记住you already have the correct head node of the rest of the list, 然后处理好当前head阶段的算法就行了;
然后有人给出iterative的做法:
@ofLucas said in Short but recursive Java code with comments:
Check this out. 16 Lines Non-recursive.
public ListNode reverseKGroup(ListNode head, int k) {
int n = 0;
for (ListNode i = head; i != null; n++, i = i.next);
ListNode dmy = new ListNode(0);
dmy.next = head;
for(ListNode prev = dmy, tail = head; n >= k; n -= k) {
for (int i = 1; i < k; i++) {
ListNode next = tail.next.next;
tail.next.next = prev.next;
prev.next = tail.next;
tail.next = next;
}
prev = tail;
tail = tail.next;
}
return dmy.next;
}
花了图才看懂, 他这个invert的逻辑真的是相当的复杂了, 特别绕人. 暂时没有看到什么值得学习的地方. 注意他这里.next.next这种连续advance的方式是我一直不喜欢的方式, 但是他这里之所以能够安全的使用, 是因为他提前一个pass找到了总长度n, 这样在header里面就可以保证, 只要当前iteration可以进行, 那么我们的这个k至少是
我看完了他这个方法之后尝试把我的方法里面的fast给消掉, 但是没有办法做到, 然后才发现他这个方法的厉害之处. 他这里没有维护fast, 但是还是可以顺利的invert;
看完了他这个做法的启发之后, 我也尝试把我的fast拿掉, 写出来这个算法:
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (k == 1 || head == null)
return head;
ListNode dummy = new ListNode (0), cur = head, prev = dummy;
dummy.next = head;
while (cur != null) {
invert (cur, prev, k);
// advance
prev = cur;
cur = cur.next;
}
return dummy.next;
}
void invert (ListNode head, ListNode parent, int k) {
ListNode cur = head, prev = null;
for (int i = 0; i < k && cur != null; i++) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
parent.next = prev;
head.next = cur;
}
}
但是这个算法是错的, 一旦remainder部分的长度超过1, 那么最后在你发现你是在remainder的时候, 已经来不及了, 因为你已经invert掉几个node了; 这时候要是重新undo, 就很麻烦; 这个也是为什么他的写法里面, 一开始要算长度, 不然最后的remainder的iteration, 进去了之后就很难处理了;
@reeclapple said in Share my Java Solution with comments in line:
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head==null||head.next==null||k<2) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode tail = dummy, prev = dummy,temp;
int count;
while(true){
count =k;
while(count>0&&tail!=null){
count--;
tail=tail.next;
}
if (tail==null) break;//Has reached the end
head=prev.next;//for next cycle
// prev-->temp-->...--->....--->tail-->....
// Delete @temp and insert to the next position of @tail
// prev-->...-->...-->tail-->head-->...
// Assign @temp to the next node of @prev
// prev-->temp-->...-->tail-->...-->...
// Keep doing until @tail is the next node of @prev
while(prev.next!=tail){
temp=prev.next;//Assign
prev.next=temp.next;//Delete
temp.next=tail.next;
tail.next=temp;//Insert
}
tail=head;
prev=head;
}
return dummy.next;
}
}
意识到remainder问题的不好解决之后, 这个人用的是另外一个思路, 每一个window都先验证一下长度得到K; 这个也可以, 不过跟上面那个人先整体走一遍是没有多大区别的;
@fieryoOo said in [20\-line iterative C\+\+ solution](https://discuss.leetcode.com/post/104629):
> There's no need for the dummy head if a 'pointer to the pointer' is used. Plus we can avoid checking the remaining length (which effectively causes the list to be traversed twice instead of once) by simply reversing the last segment back when the end is reached:
>
```c++
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if( k > 1 ) for(auto pp=&head; *pp;) pp = reverse(pp, k);
return head;
}
private:
ListNode** reverse(ListNode** pphead, int k) {
auto ppnew = &((*pphead)->next);
for(int kr=1; kr<k; kr++) {
if( ! *ppnew ) return reverse(pphead, kr);
auto pnext = (*ppnew)->next;
(*ppnew)->next = *pphead;
*pphead = *ppnew;
*ppnew = pnext;
}
return ppnew;
}
};
这个undo的思路我也是有的, 不过不是很有把握能做对; 想了一下, 好像是能写的; 最后想了想办法, 就是最上面那个版本了; 不过速度其实并没有提升;
submission波动内最优解:8(24):
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode cur = head;
int n = 0;
while (cur != null && n != k) {
cur = cur.next;
n++;
}
if (n == k) {
cur = reverseKGroup(cur, k);
while (n-->0) {
ListNode nex = head.next;
head.next = cur;
cur = head;
head = nex;
}
head = cur;
}
return head;
}
}
recursion算法还是快;
Problem 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
Difficulty:Hard
Total Accepted:116.7K
Total Submissions:373.6K
Contributor:LeetCode
Companies
facebookmicrosoft
Related Topics
linked list
Similar Questions
Swap Nodes in Pairs