Skip to content

92. Reverse Linked List II

Linked List

Problem - Reverse Linked List II

Medium

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 <= 500
  • 1 <= left <= right <= n

 

Follow up: Could you do it in one pass?

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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]:
        if head.next is None or left == right:
            return head
        dummy = ListNode(next=head)
        last = dummy
        for _ in range(left - 1):
            last = last.next

        head1, head2 = last, last.next
        current = head2
        for _ in range(right - left + 1):
            temp = current.next
            current.next = last
            last, current = current, temp

        head1.next = last
        head2.next = current
        return dummy.next

Submission Stats:

  • Runtime: 0 ms (100.00%)
  • Memory: 17.7 MB (85.17%)