题目描述
输入一个链表,反转链表后,输出新链表的表头。
思路
思路1:暴力,直接将头一个个往后移动
思路2:头插法——记住表头,从第二个开始,一个个插到表头
头插法详细的图表描述
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHL1UleNFTWU5EeRpHW4Z0MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnLwQTMwIzMzkDM1AjMwEjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
实现
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
//边界条件判断,保证至少有两个结点;没有结点或者只有1个结点就直接返回
if (!pHead||!pHead->next) return pHead;
ListNode* p1=pHead;
ListNode* p2=pHead->next;
while (p2)
{
ListNode* p=p2->next;//保存p2next的信息
p2->next=pHead;//调整指向,将p2的next指向头
p1->next=p;//调整指向,将p1的next指向原来p2的next,即p
pHead=p2;//调整定位指针,pHead永远指向头
p2=p1->next;//调整定位指针,p2又重新指向p1的下一个,准备下一轮循环
}
return pHead;
}
};