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

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

[c language=”++”]
/**
* 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;
}
};
[/c]

方法二：就地翻转

[c language=”++”]
/**
* 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;
}
};
[/c]