数据结构-反转链表

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

分析：确保输入的链表头指针为NULL或者整个链表就一个节点的情况

/*
剑指offer面试题16
*/
#include <iostream>
#include <stack>

using namespace std;

struct ListNode{
    ListNode* Next;
    int data;
};

/*
自己的写的代码就是难看！
*/
ListNode* ReverseList(ListNode** head){
    if(*head == NULL){
        return NULL;
    }
    if((*head)->Next == NULL){  //当只有一个节点的时候，容易忽略
        return *head;
    }
    ListNode* p = *head;
    stack<ListNode*> s;

    while(p != NULL){
        s.push(p);
        p = p->Next;
    }

    ListNode* q = new ListNode;
    q = s.top();
    s.pop();
    ListNode* k = new ListNode;
    k = s.top();
    s.pop();
    q->Next = k;
    while(!s.empty()){
        k->Next = s.top();
        k = k->Next;
        s.pop();
    }
    k->Next = NULL;
    return q;
}

/*
代码简洁的思路是一个一个断裂，然后组合。
*/
ListNode* ReverseList1(ListNode** head){
    ListNode* pReHead = NULL;
    ListNode* p = *head;
    ListNode* pPrev = NULL;

    while(p != NULL){
        ListNode* pNext = p->Next;

        if(pNext == NULL){
            pReHead = p;
        }

        p->Next = pPrev;
        pPrev = p;
        p = pNext;
    }
    return pReHead;
}


int main()
{
    ListNode* head = new ListNode;
    ListNode* One = new ListNode;
    ListNode* Two = new ListNode;
    ListNode* tail = new ListNode;

    head->data = 0;
    head->Next = One;
    One->data = 1;
    One->Next = Two;
    Two->data = 2;
    Two->Next = tail;
    tail->data = 3;
    tail->Next = NULL;

    //ListNode* result = ReverseList(&head);

    ListNode* result1 = ReverseList1(&head);

    while(result1 != NULL){
        cout << result1->data << " ";
        result1 = result1->Next;
    }

    return 0;
}