题解 | #反转链表#
反转链表
https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { if (pHead == nullptr) { return nullptr; } ListNode * pre = nullptr; ListNode * now = pHead; ListNode * next = nullptr; while (now != nullptr) { next = now->next; now->next = pre; pre = now; now = next; } return pre; } };
单链表反转,一般都是通过多个指针辅助,将节点的next指针指向前一个节点。关键在于当前节点如果直接改变了next指针的指向,则会丢失掉该节点next指针原本指向的节点,故所以需要借助额外的临时指针变量保存原本的next指向的节点。
还有另外一种实现,利用递归实现反转链表:
node* ReverseList(node* pHead) {
if (pHead == nullptr || pHead->next == nullptr)
return pHead;
node * temp = ReverseList(pHead->next);
pHead->next->next = pHead;
pHead->next = nullptr;
return temp;
}
传入头节点,通过递归返回最后一个节点的地址,然后在递归函数中一个个将节点的next指向反转