Reverse a singly linked list.

 

代码如下：

the iterative solution：（c++）

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode* reverseList(ListNode* head) {        ListNode *temp = NULL , *nextNode = NULL;        while(head){            nextNode = head->next;   //save the current's next node             head->next = temp;      //let the current point to its previous one            temp = head;           //save the current node as pre            head = nextNode;      //move to next node        }        return temp;            //just point to the last node we wanted    }};

　或：

class Solution {    public:        ListNode *reverseList(ListNode *head){    if (head == NULL || head->next == NULL)        return head;    ListNode *pCurr = head;    ListNode *pPrev = NULL;    ListNode *pNext = NULL;    while (pCurr != NULL)    {        pNext = pCurr->next;  //save next node        pCurr->next = pPrev;        if (pNext == NULL)            head = pCurr;        pPrev = pCurr;        pCurr = pNext;    }    return head;}    };

　　

　

其他解法：

 1、 the recursive version：（c++）

class Solution {public:    ListNode* reverseList(ListNode* head) {        if (head == NULL || head->next == NULL) return head;   // case proof and recursion exit conditon        ListNode *np = reverseList(head->next);        head->next->next = head;         // make the next node point back to the node itself        head->next = NULL;               // destroy the former pointer        return np;    }};

　2、（c++）

class Solution {    public:        ListNode* reverseList(ListNode* head) {            stack
     
       s;            ListNode *tail=NULL;            while(head)            {                s.push(head);                head=head->next;            }            if(!s.empty())            head=s.top();            while(!s.empty())            {                tail=s.top();                s.pop();                if(!s.empty())                tail->next=s.top();                else                tail->next=NULL;            }            return head;        }    };
     

　　3、（c）

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */struct ListNode* reverseList(struct ListNode* head) {        struct ListNode* last = 0;        while (head)        {            struct ListNode* next = head->next;            head->next = last;            last = head;            head = next;        };        return last;    }

　或：

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */struct ListNode* reverseList(struct ListNode* head) {    if (!head)        return NULL;    struct ListNode *curr = head;    struct ListNode *next = NULL;    struct ListNode *prev = NULL;    while (curr){        next = curr->next;        curr->next = prev;        prev = curr;        curr = next;        head = prev;    }    return head;}

　　

　更多：http://blog.chinaunix.net/uid-7471615-id-83821.html