大牛们帮忙，Rverse Nodes in k-Group - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

大牛们帮忙，Rverse Nodes in k-Group

大牛们帮忙，Rverse Nodes in k-Group# JobHunting - 待字闺中

h*o2012-11-21 08:11

1 楼

Rverse Nodes in k-Group：
看了好久，没发现问题在哪儿，求大牛们过目~~
谢了！
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// Start typing your Java solution below
// DO NOT write main() function
if(head==null)
return null;
ListNode begin=head;
ListNode pre=null;

ListNode end=null;
while(begin!=null){
ListNode cur=begin;
for(int i=0;icur=cur.next;
if(cur==null)
return head;
}
end=cur;
ListNode temp=cur.next;
if(pre!=null){
pre.next=end;
}
else
head=end;

ListNode connect= reverseLinkedList(begin, end);
pre=connect;
begin=temp;

}
return head;

}
private ListNode reverseLinkedList(ListNode begin, ListNode end){
ListNode pre=null;
ListNode cur=begin;
while(cur!=end){
ListNode next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
cur.next=pre;
return begin;

}
}

l*b2012-11-21 08:11

2 楼

不是大牛，学习中，C++写的一个。。。用指针的指针很爽，java里貌似没指针，只有
reference?
ListNode *reverseKGroup(ListNode *head, int k) {
if((k < 2) || (NULL == head)) return head;
ListNode *t = head;
int i = 1;
while((t=t->next) != NULL)
++i;
i /= k;
ListNode **h = &head;
while (i-- > 0)
h = revK(h, k);
return head;
}
ListNode **revK(ListNode **h, int k) {
ListNode *t = *h, *c = t->next;
while(--k > 0) {
t->next = c->next;
c->next = *h;
*h = c;
c = t->next;
}
return &(t->next); // This is the tail.
}

R*i2012-11-21 08:11

3 楼

我不是大牛，也不懂java，看了一下楼主的代码，感觉没什么大问题，就是这个地方有
点问题：
if(cur==null)
return head;
==〉
if(cur==null){
pre.next = begin;
return head;
}
否则，最后一截就没有了。

R*i2012-11-21 08:11

4 楼

我用C++测试了一下，好象没问题。
class ListNode
{
public:
int value;
ListNode *next;
ListNode(int v)
{
value = v;
next = 0;
}
};
ListNode* reverseKGroup(ListNode*, int);
ListNode* reverseLinkedList(ListNode*, ListNode*);
void main()
{
ListNode *ln = new ListNode(1);
ListNode *cur = ln;
for(int i=2; i<=11; i++)
{
ListNode *lnNew = new ListNode(i);
cur->next = lnNew;
cur = lnNew;
}
ln = reverseKGroup(ln, 4);
}
ListNode* reverseKGroup(ListNode *head, int k) {
// Start typing your Java solution below
// DO NOT write main() function
if(head==0)
return 0;
ListNode *begin=head;
ListNode *pre=0;

ListNode *end=0;
while(begin!=0){
ListNode *cur=begin;
for(int i=0;icur=cur->next;
if(cur==0)
{
pre->next = begin;
return head;
}
}
end=cur;
ListNode *temp=cur->next;
if(pre!=0){
pre->next=end;
}
else
head=end;

ListNode *connect= reverseLinkedList(begin, end);
pre=connect;
begin=temp;

}
return head;

}
ListNode* reverseLinkedList(ListNode *begin, ListNode *end){
ListNode *pre=0;
ListNode *cur=begin;
while(cur!=end){
ListNode *next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
cur->next=pre;
return begin;

}

h*o2012-11-21 08:11

5 楼

谢了。
好像那地方是有错。
不过java过不了large judge，总是 runtime error！
非常感谢！

【在 R*****i 的大作中提到】