0092-reverse-linked-list-ii¶
Try it on leetcode
Description¶
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]
Constraints:
- The number of nodes in the list is
n. 1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
Follow up: Could you do it in one pass?
Solution(Python)¶
# 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]:
# head = [1,2,3,4,5], left = 2, right = 4
# [1,4,3,2,5]
# reverse start reverse each step prev -> cur -> next --> prev -> next -> cur
# cnt = 0
# till left - 1 inc cnt
# from left till right reverse elements
#
# cnt < left ; prev = dummy
# cnt = 0 ; prev = dummy 1,2,3,4,5
# cnt = 1 ; prev = 0 ...
# cnt = 2 ; prev = 1 ; 1 -> 3 3 -> 2 2-> 4 1 3 2 4 5
# cnt = 3; prev = 2; cur = 4 2
#
# cur_idx = 0
# tille left - 1 inc cur_idx
# from left to right
# PREV CUR
#
# 0..n-1 -> [] 1 2 3 4 5
# [] <- 1 2 3 4 5
# -<2
# next
# prev -> cur -> next
# cur -> prev
# prev -> next
# cur -> prev -> next
if not head or left == right:
return head
sentinel = ListNode()
sentinel.next = head
prev = sentinel
for _ in range(left - 1):
prev = prev.next
cur = prev.next
for _ in range(left, right):
next_ = cur.next
cur.next = next_.next
next_.next = prev.next
prev.next = next_
return sentinel.next