java - 我在反转这个链表的一部分时做错了什么？

Question

我正在尝试使用以下方法反转链接列表。

public void reversePart(int start, int end){

    if(start > end || end >size || start <0)
        throw new IllegalArgumentException("Invalid indices provided!");

    int count = end-start;
    LinkedListNode<Integer> tmp = head;
    LinkedListNode<Integer> reversalEnd = head;

    //skip start nodes;
    while(start>0){
        tmp=tmp.next;
        start--;
    }
//point where we need to reconnect the list.
    while(end>0){
        end--;
        reversalEnd=reversalEnd.next;//prepare reversal end node to connect to reversalEnd .
    }
    reversalEnd= reversalEnd.next;
    LinkedListNode<Integer> startRev= tmp;

    LinkedListNode<Integer> prev= null;
    LinkedListNode<Integer> nxt= null;
    //reverseSubList
    while(count>0){
        count--;
        nxt= startRev.next;
        startRev.next=prev;
        prev = startRev;
        if(count ==0)
            break;
        startRev=nxt;
    }
    tmp.next=startRev;// debugger crashes here. 
    nxt.next=reversalEnd;   
}

当我运行该程序时，它会无限期地运行，在尝试调试时，我注意到它按预期运行，直到反转完成并且调试器似乎在标记行处崩溃。

任何关于我做错了什么的想法将不胜感激。

Answer 1

正如你所说，逆转有效，但最终的重新附着失败了。

假设以下列表:[1,2,3,4,5,6,7,8,9,10]。当您到达 tmp.next=startRev; 时，变量如下所示:

tmp = 5,null;
reversalEnd = 9,10,null;
startRev = 7,6,5,null;
prev = 7,6,5,null;
nxt = 8,9,10,null;

null表示没有next。

这里要注意的重要点是，保存值5的node被多个变量引用，特别是tmp & 在 startRev 的第三个元素中。 IE。两者都指向完全相同的节点。

因此，当执行 tmp.next=startRev; 时，5 现在将指向 7 next。 7指向6，6指向5，与5相同> 从一开始。所以，你自己得到了一个循环。

5,7,6,5,7,6,5,7,6,5,7,6,5,7,6,5,7,6,5,7,6,5,7,6,5,7,6,5,7,6,5,7,6,5...

这就是调试器崩溃的原因。您只需在节点 4 而不是 5 处重新附加 startRev 即可。因此，除了 tmp 之外，还有一个 prevTmp。

另请注意，剩余元素 (8,9,10) 会丢失或与主列表断开连接。因此，要重新连接它们，您需要节点 5 的引用并将其附加到其 next。 tmp 在这里会派上用场。

希望我能正确解释你哪里出了问题。