206. 反转链表

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解答

思路

• cur 表示当前遍历到的节点
• pre 表示上一个节点
• 把当前节点 cur 的 next 修改为上一个节点 pre
• 注意修改前需要存储 cur->next
• 修改完成之后，把 pre 更新成 cur，把 cur 更新成 nxt，准备遍历下一个节点
• 直到把所有节点都遍历完，此时 cur = nullptr，而 pre 为头节点

复杂度：

• 时间复杂度为 $O(n)$
• 空间复杂度为 $O(1)$

代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;

        while (cur) {
            ListNode* nxt = cur->next;
            
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }

        return pre;
    }
};

Python 代码

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None
        cur = head
        
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        
        return pre

小技巧：

• 碰到指针还是审慎使用 auto，例如 nullptr_t 就不能转换为 ListNode* 类型。