时间戳

首页 > 解决方案 > 反转单链表的特定部分，即从 m 到 n

c++ - 反转单链表的特定部分，即从 m 到 n

问题描述

如何使此代码适用于 m 的所有值，即 m = (1-10) 中的任何值 * 此代码用于反转链表的特定部分。此代码有效，但仅适用于 m<5。当我们给出值时如果 m 为 5 或大于 5，它将进入无限循环。我不知道这段代码哪里出错了。一个额外的帮助:-)，是否需要像我在析构函数中所做的那样使用 delete() 删除完整的链表:: 因为我没有看到有人这样做，但我认为它需要释放堆内存. *

#include<iostream>
using namespace std;

struct Node
{
    int data;
    Node *next=NULL;
};

class LinkedList
{
    Node *first=NULL,*last=NULL;
    int no_of_nodes=10;
    public:
    LinkedList(int[],int);
     ~LinkedList();
    void display(void);
    void reverse(int m,int n);

};

LinkedList::~LinkedList()
{
    Node *p=NULL;
    for(int i=0;i<no_of_nodes;i++)
    {
      p=first;  
      for(int j=0;j<no_of_nodes-i-1;j++)
      {
          if(p->next==last)
          {
            delete(p->next);
            p->next=NULL;
            last=p;
          }
          else
          {
               p=p->next;
          }
            
      }  
    }
    delete(first);
}

void LinkedList::reverse(int m,int n)
{
    Node *prev=NULL,*pointer_m=first,*pointer_n=first;

    //Making pointer_m to point on m-th node
    for(int i=1;i<m;i++)
    {
        prev=pointer_m;
        pointer_m=pointer_m->next;
    }



    //Making pointer_n to point on n-th node
    pointer_n=first;               
    for(int i=1;i<n;i++)
    {
        pointer_n=pointer_n->next;
    }

    // reversing the list part between m and n
    Node *p=first->next,*q=first,*r=prev;      // q and r are tailing pointers
  
    while(q!= pointer_n  && p)
    {
        r=q;
        q=p;
        p=p->next;

        q->next=r;
    }

    //fixing pointers
    prev->next=pointer_n;
    pointer_m->next=p;
}

LinkedList::LinkedList(int arr[],int n)
{
    first=new Node;
    first->data=arr[0];
    last=first;

    for(int i=1;i<n;i++)
    {
        Node *temp=new Node;
        temp->data=arr[i];
        last->next=temp;
        last=temp;
    }
}


void LinkedList::display(void)
{
    Node *p=first;
  //  cout<<"No.of nodes:: "<<no_of_nodes<<"\t\t";
    cout<<"List is:: ";
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}

int main(void)
{
    int arr[]={2,4,6,8,10,12,14,16,18,20};
    int n=sizeof(arr)/sizeof(arr[0]);

    LinkedList list(arr,n);
    list.display();
    list.reverse(5,8);
    list.display();
    return 0;
}

标签： c++linked-listreverse

解决方案

主要错误源于三个回归变量`p、q、r`的初始值设置错误。3 节点通过反向段`(m -> n)`来设置节点的反向链接。这三个应该从 `m` 开始而不是开头。

// Reversing a specific part of singly Linked List i.e from m=3 to n=7
#include<iostream>
using namespace std;

struct Node
{
    int data;
    Node *next=NULL;
};

class LinkedList
{
    Node *first=NULL,*last=NULL;
    int no_of_nodes=10;
    public:
    LinkedList(int[],int);
     ~LinkedList();
    void display(void);
    void reverse(int m,int n);
};

LinkedList::~LinkedList()
{
    Node *p=NULL;
    for(int i=0;i<no_of_nodes;i++)
    {
      p=first;
      for(int j=0;j<no_of_nodes-i-1;j++)
      {
          if(p->next==last)
         {
              delete &(p->next->data);
              p->next=NULL;
              last=p;
              break;
          }
          else
          {
              p = p->next;
          }
      }
    }
    delete &(first->data);
    first = NULL;
}

void LinkedList::reverse(int m,int n)
{
    Node *prev_m, *pointer_m, *pointer_n;
    if (n >= no_of_nodes) n = no_of_nodes - 1;
    //Making pointer_m to point on m-th node
    prev_m = first;
    for(int i=1;i<m;i++) prev_m = prev_m->next;
    pointer_m = prev_m->next;
    //Making pointer_n to point on n-th node
    pointer_n=first;
    for(int i=0;i<n;i++) pointer_n = pointer_n->next;
    //  reversing the list part between m and n
    Node *p, *q, *r;
     r = pointer_m;
     q = r->next;
     p = q->next;      // q and r are tailing pointers
     q->next = r;
     while(q!= pointer_n  && p != last)
      {
         r = q;
         q = p;
         p = p->next;
         q->next = r;
      }
     //fixing pointers
     if(m!=1)
{
    prev->next=pointer_n;
    pointer_m->next=p;
}
else
{
    first=pointer_n;
    pointer_m->next=p;
}
  }
 
 LinkedList::LinkedList(int arr[],int n)
 {
    Node *temp;
    first = new Node;
    first->data = arr[0];
    last = first;

    for(int i=1 ;i<n; i++)
    {
        temp = new Node;
        temp->data = arr[i];
        last->next = temp;
        last = temp;
    }
    no_of_nodes = n;
}

 
void LinkedList::display(void)
{
   Node *p; p = first;
   cout<<"List is:: ";
   while(p != last)
   {
       cout<< (p->data) <<" ";
       p = p->next;
   }
   cout<< last->data << endl;
}

int main(void)
{
    int arr[]={2,4,6,8,10,12,14,16,18,20};
    int n=sizeof(arr)/sizeof(arr[0]);

    LinkedList list(arr,n);
    list.display();
    list.reverse(3,7);
    list.display();
    return 0;
}

测试运行将节点从 3 反转到 7。

$ ./a.exe
List is:: 2 4 6 8 10 12 14 16 18 20
List is:: 2 4 6 16 14 12 10 8 18 20

推荐阅读