206. Reverse Linked List（只需新建两个指针，借用传入的head指针，共使用三个指针）

方法一：相当于头插法，不断地把后面的节点插入到头部的next位置，思路是先反转头结点后面的节点，最后再把头结点添加到末尾。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * 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* first=head->next;//第一个翻转的节点
        ListNode* tmp;//过度节点
        
        while(first->next)
        {
            tmp=first->next;
            first->next=tmp->next;
            tmp->next=head->next;
            head->next=tmp;
        }
        
        //这个时候first为现在最后的节点，head->next为元链表最后的节点
        tmp=head->next;
        head->next=NULL;
        first->next=head;
        return tmp;
    }
};

方法二：就地翻转

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