数据结构单链表

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"节点的指针传递给每个后续的递归层。