Date and Time: Jul 30, 2024, 23:59 (EST)
Link: https://leetcode.com/problems/reverse-linked-list-ii/
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:
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Example 2:
Input: head = [5], left = 1, right = 1
Output: [5]
-
The number of nodes in the list is
n
. -
1 <= n <= 500
-
-500 <= Node.val <= 500
-
1 <= left <= right <= n
-
Save the node before
left
to beleftPrev
, we initializeleftPrev
withdummy = ListNode(0, head)
so that we can use a for loop to reach the node beforeleft
inrange(left - 1)
. -
We use the method in 206. Reverse Linked List to reverse the links of all the nodes between
left
andright
. -
Finally, we relink
leftPrev.next
toright
node, and the previousleft
node next to behead.next
. (We have to updateleftPrev.next.next
beforeleftPrev.next
, so it won't change the reversed linked list)
# 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]:
dummy = ListNode(0, head)
leftPrev = dummy
# Move until left
for _ in range(left - 1):
leftPrev, head = head, head.next
prev = None
for _ in range(right - left + 1):
tmp = head.next
head.next = prev
prev = head
head = tmp
# Relink all nodes together
leftPrev.next.next = head
leftPrev.next = prev
return dummy.next
Time Complexity:
Space Complexity:
/**
* 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) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* leftPrev = dummy;
for (int i = 0; i < left-1; i++) {
leftPrev = leftPrev->next;
head = head->next;
}
ListNode* prev = new ListNode(0); // Initialize with 0 to be null
for (int i = 0; i < right - left + 1; i++) {
ListNode* tmp = head->next;
head->next = prev;
prev = head;
head = tmp;
}
leftPrev->next->next = head;
leftPrev->next = prev;
return dummy->next;
}
};
Language | Runtime | Memory |
---|---|---|
Python3 | 39 ms | 16.6 MB |
Java | ms | MB |
C++ | 5 ms | 10.6 MB |