c++中仅使用节点指针的反向链表

Question

老师留下了这个任务:

仅通过操作每个节点中的指针来反转链表元素的顺序。不允许这样移动项，也不允许为此操作创建新节点。

我试图在这个解决方案中思考，但每次我最终需要创建一个新的节点指针或调用另一个方法，返回一个创建的。

下面是一些代码，列表是单链接的，"first"是列表的头，"last"是列表的最后一个指针。

我获取节点指针的方法:

template <class T>
Node<T>* LinkedList<T>::getNode(unsigned int i)
{
    int index = 0;
    if (i == 0)
        return first;
    Node<T>* cursor = first;
    while (index != i && cursor)
    {
        cursor = cursor->getNext();
        ++index;
    }
    return cursor;
}

还有，这是我的方法来反转列表:

template <class T>
void LinkedList<T>::reverse()
{
    int i = 1, j = 2;
    while(j <= size)
    {
        getNode(size - 1)->setNext(getNode(size - j++));
        if (j == size + 1)
            first = getNode(size - (j - 2));
        else
            getNode(size - j)->setNext(getNode(size - i++));
        getNode(size - 1)->setNext(nullptr);
    }
    last = getNode(size - 1);
}

正如我之前所说，我需要知道是否有一种方法可以让我在不使用get方法(该方法创建节点指针)的情况下完成相同的操作。我认为，当他提到创建一个新节点时，他指的是一个节点指针，因为你不能创建一个节点(一个对象，而不是指针)，并给它分配一个列表的指针。

如果有办法，如果有人分享，我会很感激，如果没有办法，那我就按正常的方式做。

Answer 1

单链表

在我看来，最简单的方法是创建一个新的头指针，然后将现有列表中的元素推入到新列表的顶部。

         +---+     +---+     +---+  
Head --> | A | --> | B | --> | C |  
         +---+     +---+     +---+  

移动第一个节点到新列表:

             +---+    
New List --> | A |    
             +---+   
         +---+     +---+  
Head --> | B | --> | C |  
         +---+     +---+  

将下一个节点推入新列表。

             +---+     +---+    
New List --> | B | --> | A |    
             +---+     +---+     
         +---+  
Head --> | C |  
         +---+  

重复，直到原列表中的所有节点都被推入新列表:

             +---+     +---+     +---+    
New List --> | C | --> | B | --> | A |    
             +---+     +---+     +---+     

实际编码留给op作为练习。
注意:只有节点中的指针发生了变化。实际节点数据没有被更改或移动。

双链表

在双重链表中，需要将下一个指针与"previous"指针交换。

           +-----+  +-----+  +-----+  
Head   --> |  A  |  |  B  |  |  C  |  
           +-----+  +-----+  +-----+  
(Previous) |  /  |  | <-- |  + <-- |  
           +-----+  +-----+  +-----+  
(Next)     | --> |  | --> |  |  /  |  
           +-----+  +-----+  +-----+  

交换后:

           +-----+  +-----+  +-----+  
           |  A  |  |  B  |  |  C  |  <-- Head  
           +-----+  +-----+  +-----+  
(Previous) | --> |  | --> |  |  /  |  
           +-----+  +-----+  +-----+  
(Next)     |  /  |  | <-- |  + <-- |  
           +-----+  +-----+  +-----+  

单链表示例代码

struct Node
{
  int data;
  Node * p_next;
};
void Reverse_List(Node * & p_list)
{
  Node * p_new_list = NULL;
  while (p_list != NULL)
  {
    // Disconnect node from original list.
    Node * p_node = p_list;
    p_list = p_node->p_next;
    p_node->p_next = NULL;
    // Push node to new list
    p_node->p_next = p_new_list;
    p_new_list = p_node;
  }
  //  Set passed pointer to new list
  p_list = p_new_list;
}

使代码泛型是留给op的练习。