思路:利用三个指针的动作完成链表的逆转,接下来以一个实例作讲解
1、ListNode *prev = nullptr, *curr = head; // prev 指向一个空指针,curr指向链表首元素
2、while (curr) {...} // 判断curr是否为空,不为空则进入逆转循环
3、 ListNode *nextTemp = curr->next; // 逆转后curr->next会丢失,故先将其保存到next中
4、curr->next = prev; // 逆转curr与prev
5、prev = curr; curr = nextTemp; // 平移prev与curr以进行下一次逆转,此时curr与next指向同一节点
6、while (curr) {...} // 跳转whie处判断curr是否为空,不为空则继续进行逆转循环
.....
结束时链表状态,curr指空,while循环跳出,prev指向逆转后链表头节点。
代码:
// 返回逆转后的链表头结点ListNode* _ReverseList(ListNode *head) { ListNode *prev = nullptr, *curr = head; while (curr) { // prev与curr反转之前先保存curr的下一个位置 ListNode *nextTemp = curr->next; // 逆转curr与prev curr->next = prev; // 移动prev与curr prev = curr; curr = nextTemp; } return prev;}
动态图: