剑指offer系列——15.反转链表

Q：输入一个链表，反转链表后，输出新链表的表头。
C：时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
T：
1.常规的反转链表方法

    ListNode* ReverseList(ListNode* pHead) {
        ListNode *temp = pHead;
        ListNode *target = temp;
        if (pHead == nullptr)
            return pHead;
        while (pHead->next != nullptr) {
            temp = pHead->next;
            pHead->next = temp->next;
            temp->next = target;
            target = temp;
        }
        return target;
    }

2.递归：递归的方法其实是非常巧的，它利用递归走到链表的末端，然后再更新每一个node的next 值 ，实现链表的反转。而newhead 的值没有发生改变，为该链表的最后一个结点，所以，反转后，我们可以得到新链表的head.

    ListNode *ReverseList(ListNode *pHead){
        if(pHead == nullptr || pHead->next == nullptr)
            return pHead;
        ListNode* target = ReverseList(pHead->next);
        pHead->next->next = pHead;
        pHead->next = nullptr;
        return target;
    }

3.利用栈：

    ListNode* ReverseList(ListNode* pHead) {
        stack<int> s;
        ListNode* target = pHead;
        while(target){
            int temp = target->val;
            s.push(temp);
            target = target->next;
        }
        target = pHead;
        while(!s.empty()){
            int t = s.top();
            s.pop();
            target->val = t;
            target = target->next;
        }
        return pHead;
    }

剑指offer系列——15.反转链表

原文：https://www.cnblogs.com/xym4869/p/12253410.html