How can I reverse a linked list iteratively?

You can reverse the list iteratively by using three pointers: previous, current, and next. Traverse the list, updating each node's next pointer.

What is the time complexity of reversing a linked list?

Reversing the list takes O(n) time, where n is the number of nodes, because each node is visited once.

Why is the recursive solution slower than the iterative one?

The recursive solution has the same time complexity as the iterative one, but it uses additional memory due to the function call stack.

How do I handle an empty list in this problem?

If the list is empty, simply return the head as null without performing any reversal, as there's nothing to reverse.

What is the iterative method's advantage over the recursive one?

The iterative method uses constant space (O(1)), making it more memory-efficient compared to the recursive method, which uses O(n) space.

#206

Easy

auto_awesome链表·链表

LeetCode 题解工作台

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。示例 1：输入： head = [1,2,3,4,5] 输出： [5,4,3,2,1] 示例 2：输入： head = [1,2] 输出： [2,1] 示例 3：输入： head = [] 输出： [] 提示：链表中节点的数…

链表递归

题目描述

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

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

lightbulb

解题思路

方法一：头插法

我们创建一个虚拟头节点 $\textit{dummy}$ ，然后遍历链表，将每个节点依次插入 $\textit{dummy}$ 的下一个节点。遍历结束，返回 $\textit{dummy.next}$ 。

时间复杂度 $O(n)$ ，其中 $n$ 为链表的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        dummy = ListNode()
        curr = head
        while curr:
            next = curr.next
            curr.next = dummy.next
            dummy.next = curr
            curr = next
        return dummy.next

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1) for the iterative solution

psychology

面试官常问的追问

外企场景

question_mark
Do you know how to handle pointer updates safely without losing references to nodes?
question_mark
Can you explain the difference in space complexity between the iterative and recursive solutions?
question_mark
Are you familiar with edge cases such as empty lists or lists with only one element?

warning

常见陷阱

外企场景

error
Failing to maintain the correct order of nodes during pointer reversal, leading to lost references.
error
Overcomplicating the solution with extra data structures, which isn't needed for in-place reversal.
error
Forgetting to handle the case where the list is empty or has only one node.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Reverse a doubly linked list in place.
arrow_right_alt
Reverse a linked list in groups of k nodes.
arrow_right_alt
Reverse a linked list in a more memory-efficient way using tail recursion.

help

常见问题

外企场景

继续练习

#1 两数之和 #207 课程表