java - 双链表的反向追踪功能出现问题

Question

我有一个完整的工作方法来反转双向链表。老实说，我几个月来一直在尝试跟踪此代码以了解其工作原理，但当我使用 current.prev 更新当前节点时，我最终感到困惑

我尝试在每次更改下一个和上一个指针时打印出节点的值，但是我得到了一个空指针异常，所以没有运气。

public void reverse(){
    Node temp  = null;
    Node current = head; 

    while(current != null){
        temp = current.prev;
        current.prev = current.next;
        current.next = temp;
        current = current.prev;
    }

    if(temp != null){
        head = temp.prev;
    }
}

这里没有错误，我通过自己的测试用例测试了最坏和最好的情况。我似乎无法理解发生了什么事。我知道这本质上是交换下一个和上一个指针，但我需要知道如何交换。

Answer 1

public void reverse(){
// Create initial values
Node temp  = null;
// Note that you are using current to traverse through the linked list
Node current = head; 

// While current is not at the end of the original (non-reversed) list
while(current != null){
    // Swapping prev and next
    temp = current.prev; // temp 'temporarily' holds copy of current.prev
    current.prev = current.next; // current.prev is overwritten with current.next
    current.next = temp; // current.next is overwritten with temp (containing original current.prev)
    // You are setting current to the newly redefined prev
    // This was equal to current->next in the original (non-reversed) list
    // So you are traversing through the original list
    // Anything 'before' this has already been reversed
    // Anything 'after' still needs to be reversed
    current = current.prev;
}

// Condition checks for edge case of a one node linked list
if(temp != null){
    // Set the head of the reversed list
    head = temp.prev;
}

上面的代码被注释掉了。我不是 Java 程序员，但在 C 中，我会打印出反转之前和之后每个节点的地址，以检查我是否正确执行操作。也许，你可以使用hashcodes做类似的事情？