单链表的部分逆置问题。

Question

要求写一个函数，给定一个固定的单链表，输入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;
  }
}

Answer 1

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);
}

Answer 2

这样吧,我只写思路了.
你定义一个计数变量count,然后从List头部开始遍历List,同时count++

1. 当count<begin时,将ListElmt复制到新的NewList中
2. 当begin<=count<=end时,将每个ListElmt复制到新的NewList2中,并使后一个ListElmt的元素指针指向前一个ListElmt,最后将NewList中的最后一个ListElmt的指针指向NewList2中的最后一个ListElmt
3. 当count>end时,同count<begin的方法