c++ - 反转两个节点之间的链表

Question

我正在为 CS 类(class)做一些家庭作业，并且在一个函数上遇到了一些困难，该函数旨在反转两个给定节点之间的双向链表。我对自己做错了什么感到很困惑，我搜索了谷歌和 SO，但找不到任何可以帮助我的东西。

我有一个双向链表，我实际上是将此函数用作辅助函数，以在作为函数参数给出的两个节点之间反转它。

下面是模板的代码，注释让你知道我的思维过程

template <class T>
void List<T>::reverse( ListNode * & startPoint, ListNode * & endPoint )
{
    //make sure that none of the pointers are null and that the start and 
    //end points aren't the same
    if(startPoint == NULL || endPoint == NULL || startPoint == endPoint)
        return;
    //Make two nodes denoting everything happening before the
    //start and everything after the end
    ListNode *before = NULL;
    ListNode *after = NULL;
    if(startPoint->prev != NULL)
        before = startPoint->prev;
    if(endPoint->next != NULL)
        after = endPoint->next;
    ListNode *temp = startPoint;
    ListNode *temp2;
    //run a loop actually reversing the list. I have identified
    //that this is where the problem is happening (obviously)
    //for some reason the prev pointer for every node is being set to null
    //so if I had a linked list with 1 2 3 4 5
    //after running this it's just 5
    while(temp!=endPoint && temp!=NULL){
        temp2 = temp->next;
        if(temp->prev!=NULL);
            temp->next = temp->prev;
        if(temp2!=NULL)
            temp->prev = temp2;
        temp = temp2;

    }
    //switch around the end and start pointers
    endPoint = startPoint;
    startPoint = temp;
    //make sure it's integrated into the rest of the linked list
    if(before != NULL){
        before->next = startPoint;
        startPoint->prev = before;
    }
    if(after != NULL){
        after->prev = endPoint;
        endPoint->next = after;
    }
}

那么，有什么想法吗？ 我已经了解问题发生的位置和原因，但我不明白为什么会发生以及如何解决。

此外，如果您认为我在做一些多余或不必要的事情，请随时告诉我，我有时会那样做。

编辑:这是一个包容性函数，因此如果您在链表 {1, 2, 3, 4, 5, 6} 上调用它，并且指针指向值为 2 和 5 的节点，则链表将是更改为 {1, 5, 4, 3, 2, 6}

Answer 1

问题出在子列表的末端。

你没有给出一个完整的例子(这会有所帮助)，但假设我们从列表 {1, 2, 3, 4, 5} 开始，然后我们尝试 reverse(s, e)，其中 s 和 e 是指向 2 和 4 的指针。(所以我们想要的结果是 {1, 4, 3, 2, 5}。)

这是我在 ASCII 艺术方面的技能失败的地方，但“下一个”和“上一个”指针看起来像这样:

1-->2-->3-->4-->5

1<--2<--3<--4<--5

当控制离开 while 循环时，它们看起来像这样:

1<->2<--3   4-->5
1   2-->3<->4<--5

这几乎是我们想要的，但是进程很快就停止了一个节点(4 没有被逆转)。在“集成到列表的其余部分”之后，它们看起来像这样:

  ________ ___
 /   /    \   \
1   2<--3  >4-->5
1   2-->3-->4   5
 \___\_____/___/

不是很清楚，但是如果你从列表的开头开始向前移动，它就是 {1, 4, 5}，如果你从末尾向后移动它就是 {5, 2, 3, 4, 1}。您已经打破了双向链接条件，即如果 a.next 指向 b，则 b.prev 指向 a，反之亦然。

我的建议(除了用铅笔和纸画更多箭头之外)是从列表中删除子列表，反转它，然后将它拼接回去；试图就地扭转它是令人困惑的。