数据结构单链表

Question

假设我在一个单链表中有一个头指针H，我如何在伪代码中实现这一点？反转由H指向的单链表中的节点。注意:不能创建新节点。

Answer 1

您可以通过将问题拆分为第一个节点和其余节点，颠倒其余节点，然后将新的最后一个节点指向第一个节点来递归解决该问题。递归堆栈的每一层都从调用它的层的"rest“节点开始

reverse(node header){

//Return if empty list.
if (h == null) return

//Split the problem into first and rest.
node first = header.start
node rest = first.next

//Return if only one node.
if (rest == null) return

//reverse the rest of the problem, and then point the end of the rest to the old first.
header.start = rest
reverse(header)
first.next.next = first

//Set the old first to null, as it is now the last node in the list.
first.next = null

//Point the header H to the new first node.
H.next = rest

}

这被简化为不使用指针，如果您可以在伪代码中使用指针，则可以将指向"rest“节点的指针传递到每个后续递归层。