[LeetCode] C++ 92. Reverse Linked List II

https://leetcode.com/problems/reverse-linked-list-ii/description/

 

문제

 

문제 분석

- Linked list 뒤집기 문제에서 범위만 따로 추가된 것입니다. left에 해당하는 범위까지 이동한 뒤에 배열을 쭉 뒤집고, right 이후에는 그대로 이어붙여주면 됩니다.

 

풀이

/**
 * 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) {
        if(!head || left == right) return head;

        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* prev = dummy;

        for(int i = 1; i < left; ++i){
            prev = prev->next;
        }

        ListNode* curr = prev->next;
        ListNode* next = nullptr;
        ListNode* prevTail = curr;

        for(int i = 0; i < right - left + 1; ++i){
            next = curr->next;
            curr->next = prev->next;
            prev->next = curr;
            curr = next;
        }

        prevTail->next = curr;

        head = dummy->next;
        delete dummy;
        return head;
    }
};