剑指offer15

剑指offer15：反转链表

题目描述

题目描述
输入一个链表，反转链表后，输出新链表的表头。

解法一：基于头插法

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* h = NULL;
        for (ListNode* p = pHead; p; ) {
            ListNode* tmp = p->next;
            p->next = h;
            h = p;
            p = tmp;
        }
        return h;
    }
};

解法二：基于堆栈的方法

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (pHead == NULL || pHead->next == NULL)
        {
            return pHead;
        }
        ListNode * p = pHead;
        ListNode * newHead;
        stack<ListNode *> stack1;
        while (p->next != NULL)
        {
            stack1.push(p);
            p = p->next;
        }
        newHead = p;
        while (!stack1.empty())
        {
            p->next = stack1.top();
            p = p->next;
            stack1.pop();
        }
        p->next = NULL;
        return newHead;

    }
};