题解 | #反转链表#

反转链表：最直观的想法是，双指针，当链表为空或者链表长度为1时，返回pHead，反之，使用指针p表示头结点，使用指针q表示p的下一个结点，先将p的next指针置为空，然后当p与q均不为空时，使用指针r保存q的下一个结点，接着将p指向q颠倒为q指向p，再将p和q分别后移一位，直至q为空返回p。（在没有头结点的情况下）

ListNode* ReverseList(ListNode* pHead) 
{
	if(pHead==nullptr||pHead->next==nullptr) //空链表或者长度为一
		return pHead;
	ListNode *p=pHead,*q=pHead->next,*r=nullptr;
	p->next=nullptr; //头结点的下一个结点置为空
	while(p&&q)
	{
		r=q->next; //保存下一个
		q->next=p; //颠倒顺序
		p=q; //指针后移
		q=r; //指针后移
	}
	return p; //反转后的链表头结点 
}

idea：头插法也是链表反转的精髓。（在有头结点的情况下）

ListNode* ReverseList(ListNode* pHead) 
{
	ListNode *head=new ListNode(-1); //头结点
	head->next=nullptr;
	ListNode *cur=pHead,*nextcur=nullptr; 
	while(cur) //当前结点不为空
	{
		nextcur=cur->next; //保存下一个
		cur->next=head->next; //头插法
		head->next=cur;
		cur=nextcur; //更新当前
	}
	return head->next; //返回反转后的头结点
}