c++ - 用 2 个指针反转链表

Question

我正在尝试仅使用两个指针创建一个链表(我看过的每篇文章似乎都使用 3 个，但我对分配的要求是 2 个)

所以我将从我是如何处理这个问题开始的。目前这些值是这样链接的 nullptr -> (head)1->2-> ... -> 7->8->nullptr，其中被反转的值是 1,2,3,4,5,6， 7,8

void reverseList(){
    ListNode *last = head;
    ListNode *current = last->next;

    if(current == nullptr) return;

    while(current != nullptr){
         current->next = last;
         last = current;
         current = last->next;
    }
}

逻辑上，在纸面上我的循环有效，但它在我的 ide 和调试器中是一个无限循环。

我还尝试制作一个循环来检查大小并从末尾开始，其中 head = 8 和 tail = 1 但这也没有用。

我还尝试了一种二进制搜索方法，我找到了中点并进行了 +- mid 和交换，但我也无法从 4->3 进行。

我的目标是从 1->2->3->4->5->6->7->8 到 8->7->6->5->4->3 ->2->1

Answer 1

让它变得更简单，改为移动 head ptr。

因为您的 display() 首先在 head 开始。

void reverseList(){
    ListNode* current = head->next;

    if(current == nullptr) return; // list is empty

    head->next = nullptr;

    while(current != nullptr) { // have we reached the end of a forward list?
        ListNode* next = current->next;
        current->next = head; // reverse next pointer to "previous" node
        head = current;       // move last pointer to "current" node
        current = next;       // move to "next" node
    }
}