为什么我的头指针在链表中发生变化，甚至没有通过引用传递它？

Question

我创建了一个链表，并创建了一个函数 reverseList，它接受一个指向头的指针和 return 指向最后一个节点的指针。

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 中传递了我的头指针。我正在提供输出图像。

Answer 1

评论已经解释的很好了，试着说明一下，让它更清楚一点：

  1 > 2 > 3 > 4 > NULL
  ^
 head

现在你反转列表，结果是：

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

因为你没有改变head，它仍然指向与列表反转之前指向的相同节点，但是在反转列表之后，这个节点现在是最后一个。

旁注：忘记重新赋值是一个很常见的错误，所以最好将链表封装在一个单独的 class:

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;
        head = head->next;
    }
    return cur;
}

注意新名称，reverse 更像是像您一样修改原始列表。

Answer 2

要创建一个新的链表，您需要创建一个新变量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;
}

为什么我的头指针在链表中发生变化，甚至没有通过引用传递它？

Why my head pointer is changing in linked list,even not passing it by reference?

c++

c++11

pointers

linked-list

null-pointer