反转链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (pHead == NULL) {
            return NULL;
        }
        //构造一个栈
        stack<ListNode*> tmp;
        ListNode *result = new ListNode(0);
        ListNode *p = result;
        while (pHead!=NULL)
        {
            tmp.push(pHead);
            pHead = pHead->next;
        }

        while (!tmp.empty())
        {
            p->next = tmp.top();
            tmp.pop();
            p= p->next;
        }
        /*遍历完成后 p->next 需要设置为NULL。
        否则链表倒数第二个结点指向第一个，倒数第一个结点指向倒数第二个结点，相互指向造成死循环。
        */
        p->next = NULL;
        return result->next;
    }
};

//用来测试代码。
void connectList(ListNode *pCurrent, ListNode *pNext) {
    if (pCurrent == NULL) {
        cout << "input *pCurrent error" << endl;
        return;
    }
    pCurrent->next = pNext;
}
int main() {
    ListNode *pNode1 =new ListNode(1);
    ListNode *pNode2 = new ListNode(2);
    ListNode *pNode3 = new ListNode(3);
    ListNode *pNode4 = new ListNode(4);
    ListNode *pNode5 = new ListNode(5);

    connectList(pNode1, pNode2);
    connectList(pNode2, pNode3);
    connectList(pNode3, pNode4);
    connectList(pNode4, pNode5);
    //用来测试
    Solution s;
    ListNode *reverse = s.ReverseList(pNode1);
    
}