题目描述
输入一个链表，反转链表后，输出新链表的表头
原理
![]()
假设正在对结点v进行反转操作，即原来结点u的next域指向v（图中已经调整完毕，现在指向前一个结点），v的next域指向w。现在要做的是将v的next域指向u。从图中我们可以看出，当把v的next指针指向u的同时，原先指向的w就已经无法被正常的访问到了，为了避免“断链”，我们必须在指针更改指向之前，保存修改结点的下一结点
同时我们也必须存储上一个结点，因为next域即将修改指向该结点。因此定义三个指针，分别指向当前遍历的结点，前一个结点和后一个结点
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| struct ListNode {
int val;
struct ListNode* next;
ListNode(int x, ListNode* ptr = nullptr) :
val(x), next(ptr) {
}
};
ListNode* ReverseList(ListNode* pHead) {
ListNode* nHead = nullptr;
ListNode* node = nullptr;
while (pHead != nullptr) {
node = pHead;
pHead = pHead->next;
node->next = nHead;
nHead = node;
}
return nHead;
}
|
输入为
输出为
