反转链表,简单易懂~
平常习惯用的是带头结点的链表,但这个题是不带头结点的链表,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) return NULL;
//头插法
ListNode *p = head->next; //p指针辅助操作
head->next = NULL;
while(p) //原链表不为空
{
ListNode *q; //用q来标记p的下一个结点,方便下次循环时使p指向正确的位置
if(p->next != NULL)
q = p->next;
else q = NULL;
p->next = head;
head = p;
p = q;
}
return head;
}
};