19.递归法和非递归法反转链表[ReverseLinkedList]

【题目】

输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。

【非递归】

 C++ Code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

listnode *Reverse_Iteratively(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;
}

【递归】

 C++ Code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

listnode *Reverse_Recursively(listnode *head)
{
    Reverse(NULL, head, NULL);
}

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

【参考】

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

个人学习笔记，欢迎拍砖!---by hellogiser

Author: hellogiser

Blog: http://www.cnblogs.com/hellogiser/

Warning: 本文版权归作者和博客园共有，欢迎转载，但请保留此段声明，且在文章页面明显位置给出原文连接。Thanks！

Me: 如果觉得本文对你有帮助的话，那么【推荐】给大家吧，希望今后能够为大家带来更好的技术文章！敬请【关注】。