Почему мой указатель головы меняется в связанном списке, даже не передавая его по ссылке? - PullRequest
Новая
       33

Почему мой указатель головы меняется в связанном списке, даже не передавая его по ссылке?

0 голосов
/ 06 июля 2018

Я создал связанный список и создал функцию reverseList, которая берет указатель на голову и возвращает указатель на последний узел. 

Node* reverseList(Node *head)
{
  Node* curr=head;
  Node* prev=NULL;
  Node* ahead;
  while(curr!=NULL)
  {
    ahead=curr->next;
    curr->next=prev;
    prev=curr;
    curr=ahead;
  }
return prev;
}

Но в основном, когда я делаю это 

int main()
{
  int n;///no of elements in list
  cin>>n;

  Node* head=NULL;
  head=createList(head,n);///creating list(it is working properly)
  printList(head);

  cout<<endl;
  Node* temp=reverseList(head);///reversing list and storing address of list in 
  //new node
  printList(temp);///printing reversed list properly

  cout<<endl;

  printList(head);///while printing this it is printing only one elements, 
  //which implies head pointer changes but I don't know
  ///how
}

Указатель моей головы меняется, и он печатает только одно значение.Я должен был передать мой указатель на голову в reverseList по значению.Я предоставляю изображение вывода.

image of output

Ответы [ 2 ]

0 голосов
/ 06 июля 2018

Чтобы создать новый связанный список, необходимо создать новую переменную Node и выполнить операции с этой переменной.

Итак, код будет выглядеть примерно так: 

Node* reverseList(Node *head)
{
    Node* newRootPtr = new Node(); //Pointer to the new root. This will be returned to the calling function.

    newRootPtr->next = NULL;        //In the reversed list, the original head will be the last node.

    Node* curr=head;                //For iterations

    while(curr->next!=NULL)         //For every node, until the last node. Note that here, we need to stop at the last node, which will become the first node of the new List.
    {
        Node ahead=*(curr->next);   //Create a new Node equal to the next node of the original list.
        Node* aheadPtr = &ahead;        //Pointer to the new node
        aheadPtr->next = newRootPtr;    //Point the new node to the previous node of the new list
        newRootPtr = aheadPtr;          //update root node
        curr=curr->next;
    }

    return newRootPtr;
}
0 голосов
/ 06 июля 2018

Комментарии уже хорошо объясняются, пытаясь проиллюстрировать это немного яснее: 

  1 > 2 > 3 > 4 > NULL
  ^
 head

Теперь вы переворачиваете список, в результате чего: 

  4 > 3 > 2 > 1 > NULL 
  ^           ^
 temp        head

Поскольку вы никогда не меняли head, он по-прежнему указывает на тот же узел, на который указывал до обращения к списку, но после обращения к списку этот узел теперь является последним.

Примечание: забыть о переназначении - довольно распространенная ошибка, поэтому рекомендуется инкапсулировать связанный список в отдельный класс: 

class LinkedList
{
    Node* _head;
public:
    class Node; // just as you have already
    void reverse() // now a member function
    {
        //reverse as you did before

        // encapsulating the assignment: (!)
        _head = newHead;
    }

    Node* head() { return _head; }
};

LinkedList l;
// ...
Node* tmp = l.head();
l.reverse();
// tmp variable points to tail...
// expecting tmp pointing to head is still an error,
// and there is no way to prevent it
// BUT the correct head can always be re-acquired:
head = l.head();

Редактировать в ответ на комментарий:

Если вы хотите создать новый список, вам нужно будет скопировать узлы: 

Node* createReversedList(Node* head)
{
    Node* cur = NULL;
    while(head)
    {
        Node* tmp = new Node(*head);
        // (provided you have an appropriate copy constructor)

        tmp->next = cur;
        cur = tmp;
    }
    return cur;
}

Обратите внимание на новое имя, reverse скорее подразумевает изменение исходного списка, как вы это сделали.

...