首页 > 代码库 > 19.反转链表

19.反转链表

http://zhedahht.blog.163.com/blog/static/2541117420073471124487/

非递归

listnode* reverse(listnode* head)
{// prev <-cur  next->...->null
    listnode* prev = NULL;
    listnode* cur = head;
    listnode* next = NULL;
    while(cur!=NULL)
    {
        next = cur->next;
        cur->next = prev;
        // update prev and cur
        prev = cur ;
        cur = next;
    }
    return prev;
}

递归调用

listnode* reverse2(listnode* head)
{
    r(NULL,head,NULL);
}

listnode* r(listnode* prev,listnode* cur,listnode* next)
{
    if (cur==NULL)
        return prev;
    next = cur->next;
    cur->next = prev;
    prev = cur;
    cur = next;
    return r(prev,cur,next);
}