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

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。 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 在这里会派上用场。

希望我能正确解释你错在哪里。

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

What am I doing wrong in reversing part of this linked list?

java

algorithm

linked-list