如何反转linkedList迭代，理解我在网上找到的代码

Question

我正在尝试编写不同的面试问题。一个非常经典的问题是反转单链表。我在网上找到了这段代码，并注释了它，但是在我们交换指针的地方，我真的不明白发生了什么。

public static LinkedList iterativeReverse(LinkedList linkedList) {
    if (linkedList == null || linkedList.next == null) {  //We check if the list is 
                                                           empty or has one node and
                                                           accordingly we return the list if it were the case
        return linkedList;
    }
    LinkedList prevNode, currNode, nextNode; //Three pointers 
    prevNode = null; // Are those pointers 
    nextNode = null; // temporary pointers for the swapping?
    currNode = linkedList; //is this the node pointing to head that is going to eventually point to null?
    while (currNode != null) {  // As long as we haven't reached the end of the list
        nextNode = currNode.next; //here it gets complicated for me, I don't understand what is happening
        currNode.next = prevNode;
        prevNode = currNode;
        currNode = nextNode;
    }
    return prevNode;
}

有没有人能告诉我如何解决这个问题?

谢谢。

Answer 1

假设您有一个这样的链表a->b->c，其中prevNode指向a, currNode指向b。

所以nextNode = currNode.next;将等价于点nextNode到c。

为了反转链表，我们需要将链接a-- ->b的方向改变为b-- ->a，如下所示:

currNode.next = prevNode;

现在，唯一剩下的工作是将prevNode更新为b，将curNode更新为c，并重复此过程。

prevNode = currNode;
currNode = nextNode;