力扣-反转链表

耗子收录于刷题

2022-12-18 约 563 字预计阅读 2 分钟

🔗 题目链接

给你单链表的头节点 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$

双指针迭代

我们可以申请两个指针，第一个指针叫 pre，最初是指向 null 的。¹

第二个指针 cur 指向 head，然后不断遍历 cur。
每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。

动画演示如下：

动画演示中其实省略了一个 tmp 变量，这个 tmp 变量会将 cur 的下一个节点保存起来。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


def reverseList(head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    # 申请两个节点，pre和 cur，pre指向None
    pre = None
    cur = head
    # 遍历链表，while循环里面的内容其实可以写成一行
    # 这里只做演示，就不搞那么骚气的写法了
    while cur:
        # 记录当前节点的下一个节点
        tmp = cur.next
        # 然后将当前节点指向pre
        cur.next = pre
        # pre和cur节点都前进一位
        pre = cur
        cur = tmp
    return pre  

复杂度分析²

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

目录

力扣-反转链表

双指针迭代