92. Reverse Linked List II
給定一個單鏈表的頭節點以及兩個整數 left 和 right，其中 left <= right，反轉從位置 left 到位置 right 的節點，並返回反轉後的鏈表。
範例 1：
輸入：head = [1,2,3,4,5], left = 2, right = 4 輸出：[1,4,3,2,5]
Python
from typing import Optional
# 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]:
# Create a dummy node to handle edge cases more easily
dummy = ListNode(0)
dummy.next = head
prev = dummy
# Move `prev` to the node just before the `left`-th node
for _ in range(left - 1):
prev = prev.next
# Start reversing the sublist
reverse_start = prev.next
then = reverse_start.next
# Perform the actual reversal between `left` and `right`
for _ in range(right - left):
reverse_start.next = then.next
then.next = prev.next
prev.next = then
then = reverse_start.next
return dummy.next
16.39MB, 32ms
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (!head) return nullptr;
// Create a dummy node to handle edge cases more easily
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* prev = dummy;
// Move `prev` to the node just before the `left`-th node
for (int i = 0; i < left - 1; ++i) {
prev = prev->next;
}
// Start reversing the sublist
ListNode* reverse_start = prev->next;
ListNode* then = reverse_start->next;
// Perform the actual reversal between `left` and `right`
for (int i = 0; i < right - left; ++i) {
reverse_start->next = then->next;
then->next = prev->next;
prev->next = then;
then = reverse_start->next;
}
ListNode* new_head = dummy->next;
delete dummy; // Clean up the dummy node
return new_head;
}
};
9.32MB, 0ms
Javascript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val);
* this.next = (next===undefined ? null : next);
* }
/**
* @param {ListNode} head
* @param {number} left
* @param {number} right
* @return {ListNode}
*/
var reverseBetween = function(head, left, right) {
if (!head) return null;
// Create a dummy node to handle edge cases more easily
let dummy = new ListNode(0);
dummy.next = head;
let prev = dummy;
// Move `prev` to the node just before the `left`-th node
for (let i = 0; i < left - 1; i++) {
prev = prev.next;
}
// Start reversing the sublist
let reverse_start = prev.next;
let then = reverse_start.next;
// Perform the actual reversal between `left` and `right`
for (let i = 0; i < right - left; i++) {
reverse_start.next = then.next;
then.next = prev.next;
prev.next = then;
then = reverse_start.next;
}
return dummy.next;
};
48.85MB, 40ms
