反转两个节点之间的链表

Question

我正在为一个CS类做一些家庭作业，并且正在努力使用一个函数来反转两个给定节点之间的双链接列表。我对自己做错了什么感到困惑，我在谷歌上搜索过，但找不到任何有帮助的东西。

我有一个双链表，我基本上使用这个函数作为辅助函数，在两个节点之间反转它，这两个节点作为函数的参数。

下面是模板的代码，有注释以便您了解我的思考过程

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}开始，我们尝试反向（s， e），其中s和e是指向2和4的指针。（所以我们想要的结果是{1, 4, 3, 2, 5}。）

这就是我ASCII art技能失败的地方，但“下一个”和“上一个”指针如下所示：

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，反之亦然。

我的建议（除了用铅笔和纸画更多的箭头）是从列表中删除子列表，将其反转，然后将其拼接回来；试图在适当的位置反转它是令人困惑的。