单向链表倒转递归解法

我的解法:


struct node *revert_recursive(struct node *n, struct node **head)
{
struct node *tail;
struct node *tmp;

if (!n->next) {
tail = n;
*head = n;
return tail;
}

tail = revert_recursive(n->next, &tmp);
*head = tmp;
tail->next = n;
n->next = NULL;
return n; /* n is new tail */
}

我的思路是递归过程中要记录new head和tail.

但实际上当解决最小问题的时候知道head了,然后递归返回的时候也就传给父问题了: “return nh”

更妙的是tail不需要保存, head->next就是tail:这点很关键,我想不到。

别人的更漂亮的解法:


struct node *revert_recursive_2(struct node *head)
{
struct node *nh;

if (head == NULL || !head->next)
return head;

nh = revert_recursive_2(head->next);
head->next->next = head; /* head->next is tail */
head->next = NULL;

return nh;
}

Leave a Reply