92. Reverse Linked List II

Problem Link

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

 

Follow up: Could you do it in one pass?

Solution

---

Python3

# 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(-1, head)
        curr, prev = head, dummy
 
        for _ in range(left - 1):
            prev = prev.next
            curr = curr.next
        
        A = None
        for _ in range(right - left + 1):
            nxt = curr.next
            curr.next = A
            A = curr
            curr = nxt
        
        prev.next.next = curr
        prev.next = A
 
        return dummy.next
 
 

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 m, int n) {
        if (m == n) return head;
        
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        
        ListNode *curr = head, *prev = dummy;
        
        for (int i = 0; i < m - 1; i++){
            curr = curr->next;
            prev = prev->next;
        }
        
        ListNode *temp = NULL;
        for (int i = 0; i < n-m+1; i++){
            ListNode* next = curr->next;
            curr->next = temp;
            temp = curr;
            curr = next;
        }
        
        prev->next->next = curr;
        prev->next = temp;
        
        return dummy->next;
    }
};