链表反转的递归和非递归

发表于 | 分类于 | | 阅读次数:

如题，给出链表反转的递归和非递归算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Node *reverse (Node *head)
{
    Node *p1=NULL,*p2=NULL,*p3=NULL;
    if(NULL == head || NULL == head->next)
        return head;
    p1=head;
    p2=p1->next;
    head->next=NULL;
    while(!p2)
    {
        p3=p2->next;
        p2->next=p1;
        p1=p2;
        p2=p3;
    }
    return p2;
};

1
2
3
4
5
6
7
8
9
10
11
Node *reverse_recursive(Node *head)
{
    if(NULL==head || NULL==head->next)
        return head;
    Node *p,*q;
    p=head->next;
    q=reverse_recursive(head->next);
    p->next=head;
    head->next=NULL;
    return q;
}