206. 反转链表

反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解题思路 1 (用栈)

用栈把链表结点依次放入栈中，放完之后，再依次从链表中取出结点，并把当前结点的next指针指向下一个结点**

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        stack<ListNode*>  listStack;
        ListNode* pre = head;
        if(head == NULL)
            return NULL;
        ListNode* post = head->next;
        pre->next = NULL;
        while(post != NULL){
            ListNode*lp = post->next;;
            //在链表上行走的前后指针
            post->next = pre;
            pre = post;
            post = lp;
        }   
        return pre;
    }
};

解题思路 2 (前后指针迭代)

用一个 post 指针和一个 pre 指针，它们的关系是 post = pre->next， 用这两个指针遍历链表，遍历过程中不断将 post 的指针反转为指向 pre， 即 post->next = pre ，从而达到最后反转整个链表
具体如下：

初始时，pre 指针指向 NULL, post 指针指向 head 结点
用一个临时变量 temp保存post的下一个结点，即 temp = post->next ，即图中的 a1 结点
然后把 post 的 next 指针调整为post->next = pre
更新 pre 为此时的 post , 即 pre = post 相当于 pre 向前移了一步，走到图中 head 结点
更新 post 为 temp , 即 post = temp , post 也向前移了一步，走到图中 a2 结点
依次类推不断迭代**

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* post = head;
        ListNode* lp;
        while(post != NULL){
            lp = post->next;;
            //在链表上行走的前后指针
            post->next = pre;
            pre = post;
            post = lp;
        }   
        return pre;
    }
};

解题思路 3 (递归)

参考 动画演示+多种解法 206. 反转链表

/**
 * 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) {
        if( head == NULL || head->next == NULL)
            return head;
        ListNode* cur = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return cur;
    }
};