Question

设计一个递归算法在O（n）时间内将一个含有n个元素的单链表逆置，要求其辅助空间为常量

Answer 1

node* reverse(node *head)
{
if(head == NULL || head->next == NULL)
{
return head;
}
node *cur = head;
node *pre = NULL;
node *tmp;
while(cur->next)
{
tmp = pre;
pre = cur;
cur = cur->next;
pre->next = tmp; //操作pre的next逆转
}
cur->next = pre; //结束时，操作cur的next逆转
return cur;
}