Reverse Linked List II
ID
92
Data Type
Linked List
Difficulty
Medium
Tags
In-place Reversal
Completed Date
May 8, 2024
Preference
💕 Like
Given the
head
of a singly linked list and two integers left
and right
where left <= right
, reverse the nodes of the list from position left
to position right
, and return the reversed list.Example 1:
![notion image](https://assets.leetcode.com/uploads/2021/02/19/rev2ex2.jpg?t=27c22a5e-afec-42d5-b484-5bf09071dfe9)
Example 2:
Constraints:
- The number of nodes in the list is
n
.
1 <= n <= 500
500 <= Node.val <= 500
1 <= left <= right <= n
Follow up: Could you do it in one pass?
题解
上面是原解,写的太罗嗦了,实际上可以简化
- 创建一个 "dummy" 节点,并且其
Next
指向head
。这个 "dummy" 节点用于处理left
等于 1 的特殊情况。
- 使用
pre
指针找到left
的前一个节点。这里的i < left-1
是为了让pre
停在left
的前一个节点。
cur
指针指向需要反转的链表的第一个节点。
- 在
i
从left
到right
的过程中,我们将cur
的下一个节点next
移动到pre
的后面,同时更新cur
和next
。这是一个常见的链表反转技巧。
- 最后返回
dummy.Next
,因为dummy
是新的头节点。
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2Fa52c2013-6d15-4168-8946-4b51c817fd35%2F9c27c06c-03dd-4a08-9720-121357697ac1%2F%25E6%2597%25A0%25E6%25A0%2587%25E9%25A2%2598.jpg?table=block&id=3d2c7e4f-3fe2-4c1c-bb93-1cec40ee1d4b&t=3d2c7e4f-3fe2-4c1c-bb93-1cec40ee1d4b&width=3358&cache=v2)