面试题16：反转链表

题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。链表定义如下：

struct ListNode{
    int value;
    ListNode* next;
    ListNode(int data=int()):value(data),next(NULL)
    {}
};

此题可以用递归和头插法来做。

递归

用递归做起来稍微复杂一点，而且会有个问题，就是当链表太长时，可能会导致系统栈溢出。

大体思路就是，当我们每递归的链表的一个节点时，如果该节点不是最后一个，就先递归反转它后面的链表，然后将该节点 push_back 到尾部，所以我们需要一个 tail 指针来表明最后一个节点。否则 return 即可。

代码如下：

ListNode* _ReverseList(ListNode* head,ListNode*& tail)
{
    if(head==NULL)
        return NULL;
    if(head->next==NULL)
    {
        tail=head;
        return head;
    }
    ListNode* tmp=_ReverseList(head->next,tail);
    tail->next=head;
    tail=tail->next;
    return tmp;
}

ListNode* ReverseList(ListNode* head)
{
    if(head==NULL)
        return NULL;
    ListNode* tail=NULL;
    ListNode* tmp=_ReverseList(head,tail);
    tail->next=NULL;
    return tmp;
}

头插法

这种方法的思想就是，我们从链表的第二个节点开始(如果有的话)，一次摘取当前节点并头插到前面已经部分反转的链表中去。需要注意的是，我们要维护三个节点指针，分别指向已经部分反转的链表头、当前节点和当前节点的下一个节点。

代码如下：

ListNode* ReverseList(ListNode* head)
{
    if(head==NULL)
        return NULL;
    ListNode* cur=head->next;
    head->next=NULL;
    ListNode* next=NULL;
    while(cur!=NULL)
    {
        next=cur->next;
        cur->next=head;
        head=cur;
        cur=next;
    }
    return head;
}

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往