92. Reverse Linked List II

Medium (Trung bình) C++ 🔗 Xem trên LeetCode

📋 Đề Bài

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?

🧠 Thuật Toán & Kỹ Thuật

Linked List (Danh sách liên kết)
⏱️ Thời gian O(n²)
💾 Không gian O(n)

💻 Lời Giải

C++ 0092-reverse-linked-list-ii.cpp 
/**
 * 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 *currNode = head;
        vector<int> v;
        
        while (currNode) {
            v.push_back(currNode->val);
            currNode = currNode->next;
        }
        
        reverse(v.begin() + left - 1, v.begin() + right);
        
        ListNode *answNode = new ListNode(0);
        currNode = answNode;
        
        for (int x : v) {
            currNode->next = new ListNode(x);
            currNode = currNode->next;
        }
        
        return answNode->next;
    }
};