What is the best approach to reverse a sublist in 'Reverse Linked List II'?

Use a dummy node, locate the node before left, iteratively reverse nodes from left to right, then reconnect the reversed segment to the rest of the list.

Can I use extra arrays or stacks for this problem?

While possible, optimal solutions use in-place pointer manipulation to meet the problem's space efficiency requirements.

How do I handle the edge case where left equals right?

No reversal is needed; the list remains unchanged, but your code should still correctly return the original head.

What pointers are critical during the reversal?

Track the previous node before the sublist, the current node being reversed, and the next node to maintain proper connections.

How can I verify the reversed segment is correct?

Walk through the list after reversal, checking that nodes between left and right are reversed and all other nodes maintain original order.

#92

Medium

auto_awesome链表指针操作

LeetCode 题解工作台

反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。示例 1：输入： head = [1,2,3,4,5], left = 2, right = 4 输出： [1,4,3,2,5]…

链表

题目描述

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

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

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

lightbulb

解题思路

方法一：模拟

定义一个虚拟头结点 dummy，指向链表的头结点 head，然后定义一个指针 pre 指向 dummy，从虚拟头结点开始遍历链表，遍历到第 left 个结点时，将 pre 指向该结点，然后从该结点开始遍历 right - left + 1 次，将遍历到的结点依次插入到 pre 的后面，最后返回 dummy.next 即可。

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(
        self, head: Optional[ListNode], left: int, right: int
    ) -> Optional[ListNode]:
        if head.next is None or left == right:
            return head
        dummy = ListNode(0, head)
        pre = dummy
        for _ in range(left - 1):
            pre = pre.next
        p, q = pre, pre.next
        cur = q
        for _ in range(right - left + 1):
            t = cur.next
            cur.next = pre
            pre, cur = cur, t
        p.next = pre
        q.next = cur
        return dummy.next

speed

复杂度分析

指标	值
时间	complexity is O(n) since each node is visited at most once during traversal and reversal. Space complexity is O(1) because the reversal is done in-place with only a few extra pointers regardless of list size.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checks if the candidate handles edge cases like left == 1 or left == right.
question_mark
Looks for in-place pointer manipulation without using extra arrays or stacks.
question_mark
Monitors how well the candidate maintains connections before and after the reversed sublist.

warning

常见陷阱

外企场景

error
Failing to handle the case where the reversal starts at the head node.
error
Incorrectly reconnecting the reversed sublist to the remaining list, breaking links.
error
Using extra memory instead of performing true in-place reversal.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Reverse nodes in groups of k instead of a single sublist, extending pointer manipulation skills.
arrow_right_alt
Reverse a sublist with possible cycles in the linked list, requiring cycle detection.
arrow_right_alt
Reverse only nodes with even values between left and right, combining conditional logic with pointer manipulation.

help

常见问题

外企场景

继续练习

#86 分隔链表 #83 删除排序链表中的重复元素 #82 删除排序链表中的重复元素 II