Reverse a singly linked list.
参考http://www.2cto.com/kf/201110/106607.html
方法1：
讲每个节点的指针指向前面就可以。
/**
* 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 *q = NULL;
// if(!(head && head->next)) return NULL;
// ListNode *p = head->next;
// head->next = NULL; // while(p)
// {
// q=p->next;
// p->next=head->next;
// head->next=p;
// p = q;
// }
// return head; if((head == NULL) || (head->next==NULL)) return head;
ListNode *p = head;
ListNode *q = p->next;
ListNode *r = NULL;
head->next = NULL;
while(q)
{
r = q->next;
q->next = p;
p = q;
q = r;
}
head = p;
return head; }
};
方法二：这个方法想了很久才发现题目中的意思head是第一个节点
/**
* 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 *q = NULL;
ListNode *p = head->next;//p位置不变 while(p->next)
{
q=p->next;
p->next = q->next;
q->next = head->next;
head->next = q;
}
p->next=head; //相当于成环
head=p->next->next; //新head变为原head的next
p->next->next=NULL; //断掉环
return head; }
};
太菜了！！！！！！
2015-8-2又重新写了一版，和第一种思路一样。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if((head==NULL) || (head->next==NULL)) return head;
ListNode *q;
ListNode *p;//p位置不变
p = head;
q = head->next;
head->next = NULL;
while(q)
{
p = q;
q = q->next;
p->next = head;
head = p;
}
head = p;
return head;
}
};