206. 反转链表

Problem: 206. 反转链表

思路

将一个节点的前一个节点变为后一个节点,需要有三个节点已知,

pre前一个节点,从nullptr开始

cur当前节点

temp下一个节点,因为在将前一个节点变为next的过程中原来的next会被断开,我们需要在这里保存,以便改变cur为next

脑瘫的错误

return pre;这里我之前写的是return cur cur 最后为null,pre才是最后一个节点

复杂度

• 时间复杂度:

$O(n)$

• 空间复杂度:

$O(1)$

Code

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while( cur != nullptr) {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};