Reverse Linked List II
|Last edited: 2024-5-9
ID
92
Data Type
Linked List
Difficulty
Medium
Tags
In-place Reversal
URL
https://leetcode.com/problems/reverse-linked-list-ii/
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
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?
 

题解

 
上面是原解，写的太罗嗦了，实际上可以简化
  1. 创建一个 "dummy" 节点，并且其 Next 指向 head。这个 "dummy" 节点用于处理 left 等于 1 的特殊情况。
  1. 使用 pre 指针找到 left 的前一个节点。这里的 i < left-1 是为了让 pre 停在 left 的前一个节点。
  1. cur 指针指向需要反转的链表的第一个节点。
  1. 在 i 从 left 到 right 的过程中，我们将 cur 的下一个节点 next 移动到 pre 的后面，同时更新 cur 和 next。这是一个常见的链表反转技巧。
  1. 最后返回 dummy.Next，因为 dummy 是新的头节点。
 
notion image