题目描述
输入一个链表，反转链表后，输出新链表的表头。
思路
- 头插法反转链表
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
ListNode* newpHead = pHead; // 头节点
ListNode* p = pHead; // 尾节点
ListNode* q; // 待插入的节点
// 一个指针指向第一个节点 newpHead
// 一个指针下一个需要插入的节点 q
// 一个指针指向最后一个的节点 p
// p->next 始终指向下一个要插入的目标
if(pHead == nullptr) return nullptr;
// 每次只反转一个节点
while(p->next != nullptr){ // 还有节点需要插入
q = p->next; // 获取要插入的节点
p->next = q->next; // 更新下一个要插入的节点
q->next = newpHead; // 更新插入节点的后继节点为头节点
newpHead = q; // 更新头节点
}
return newpHead;
}
};
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
