要求写一个函数,给定一个固定的单链表,输入begin end,将下标在两数之间的内容逆置。
如单链表0->3->6->9->12->15->18 输入 2 4 输出 0->3->12->9->6->15->18 。
已经写出逆置函数,打算把begin end作为你逆序算法的链表头和尾来处理,不过后续不知道怎么改了。。。求助各位大神了!
void reverse(int begin,int end,List *&head)
{
{
List *new1=NULL,*now,*old;
old=head;
while(old!=NULL)
{
now=old;
old=old->next;
now->next=new1;
new1=now;
}
head=new1;
}
}
Leetcode上的原题. 到这里看看吧
https://leetcode.com/discuss/questions/oj/reverse-linked-list-ii?start...
我的代码
记事本上写的, 不保证100%对...
void
reverse(int begin, int end, List *&head)
{
List *pre = *head, *after, *cur, *next, *dummy = NULL;
int count = 0;
/* put pre at begin-1 */
while(++count < begin && pre)
pre = pre->next;
if(!pre)
return;
/* put after at end */
after = pre->next;
while(count++ < end && after)
after = after->next;
if(!after)
return;
/* head needs to be updated */
if(begin == 0){
dummy = new List(-1);
dummy->next = head;
pre = dummy;
head = after;
}
/* do reverse */
cur = pre->next;
pre->next = after->next;
while(cur != after->next){
next = cur->next;
cur->next = pre->next;
pre->next = cur;
cur = next;
}
if(dummy)
delete(dummy);
}
这样吧,我只写思路了.
你定义一个计数变量count,然后从List头部开始遍历List,同时count++
- 当count<begin时,将ListElmt复制到新的NewList中
- 当begin<=count<=end时,将每个ListElmt复制到新的NewList2中,并使后一个ListElmt的元素指针指向前一个ListElmt,最后将NewList中的最后一个ListElmt的指针指向NewList2中的最后一个ListElmt
- 当count>end时,同count<begin的方法