牛客题霸-反转链表题解

反转链表：https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=117&&tqId=35000&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking

1、借助三个临时节点pre，cur，after进行迭代。

class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
    if (pHead == nullptr || pHead->next == nullptr) return pHead;
    ListNode * pre = nullptr,*cur = pHead,*after = pHead->next;
    while(cur != nullptr){
        cur->next = pre;
        pre = cur;
        cur = after;
        if(after != nullptr)
            after = after->next;
    }
    return pre;
}
};

2、头插法来做，将元素开辟在栈上，这样会避免内存泄露

ListNode* ReverseList(ListNode* pHead) {

    // 头插法
    if (pHead == nullptr || pHead->next == nullptr) return pHead;
    ListNode dummyNode = ListNode(0);
    ListNode* pre = &(dummyNode);
    pre->next = pHead;
    ListNode* cur = pHead->next;
    pHead->next = nullptr;
    //pre = cur;
    ListNode* temp = nullptr;
    while (cur != nullptr) {
        temp = cur;
        cur = cur->next;
        temp->next = pre->next;
        pre->next = temp;
    }
    return dummyNode.next;

}

个人更喜欢第二种方法，但是第一种更好理解一点哈