单链表部分逆置问题

码拜

9年 ago

题目：给定一个固定的单链表，输入两个数begin和end。将下标为begin到end之间的内容逆置。
给定的单链表为：0->2->4->6->8->10->12->14->16->18
测试数据确保begin和end不会超出单链表的长度范围，并且end>=begin
本人的代码入下：

#include <iostream>
using namespace std;
struct List
{
    int num;
    List *next;
};
List *head;
List* reverse(int begin, int end, List *&head)
{
    
    if(begin==end)return head;
    end-=begin;
    List* pre=new List;
    pre->next=head;
   
   
    for(int i=0;i<begin;i++)
        {
           pre=pre->next; 
        
        }
    List* pstart=pre->next;
    
    while(end--)
        {
            List *p=pstart->next;
            pstart->next=p->next;
            p->next=pre->next;
            pre->next=p; 
          
        
        }
    
    return pre->next;
}
List *Create()
{
    List *p = NULL;
    List *q = NULL;
    head = NULL;
    for ( int i = 0; i < 10; i++ ) {
        p = new List;
        p->num = i * 2;
        if ( head == NULL ) {
            head = p;
        }
        else {
            q->next = p;
        }
        q = p;
    }
    if ( head != NULL ) {
        q->next = NULL;
    }
    return head;
}
void displayList(List *head)
{
    while ( head != NULL ) {
        cout << head->num;
        head = head->next;
        if ( head != NULL ) {
            cout << "->";
        }
    }
    cout << endl;
}
int main() {
    Create();
    int begin, end;
    cin >> begin >> end;
    reverse(begin, end, head);
    displayList(head);
    return 0;
}

目前问题是假如输入begin=0，那么逆置后的链表0之前的数都未被输出。如输入begin=0，end=3，输出就是0->8->10->12->14->16->18。
求高手帮本人看看是什么原因？

解决方案

原因是while循环之前，pStart=head，
while之后，pStart->next 指向num=8那个节点了(这样head->next->num = 8)
所以你0前面的都没有打印出来。
假如你begin != 0; 这时候pStart != head, 这样while循环就不会影响head指针，displayList就会正常输出了。
—
帮你改成这样，你试试

List* reverse(int begin, int end, List *&head)
{
     
    if(begin==end)return head;
    end-=begin;
    List* pre=new List;
    pre->next=head;
    
    
    for(int i=0;i<begin;i++)
        {
           pre=pre->next; 
         
        }
    List* pstart=pre->next;
     
    List* tmpHead = head;
    while(end--)
        {
            List *p=pstart->next;
            pstart->next=p->next;
            p->next=pre->next;
            pre->next=p; 
           
         
        }
 
    head = tmpHead;
    return pre->next;
}

—
你这样写法不推荐的，原因是你不停的变动next指针，一般人看不懂，第二，容易出现指针错误。本人也是看了很久很久
给你优化了下reverse函数,如下：

struct List
{
    int num;
    List *next;
    void reverse(List* list)
    {
        if (list == NULL) return;
        int tmp = num;
        num = list->num;
        list->num = tmp;
    };
};
 
List *head;
 
List* getListByIndex(int index, List* list)
{
   if (NULL == list) 
       return NULL;
   if (index < 0)
       return NULL;
   if (index == 0)
       return list;
   return getListByIndex(--index,list->next);
}
List* reverse(int begin, int end, List *&head)
{
    List* beginList = NULL;
    while (begin < end) {
        beginList = getListByIndex(begin++,head);
        if (beginList) {
            beginList->reverse(getListByIndex(end--,head));
        }
    }
    return  head;
}