[LeetCode] 92. Reverse Linked List II

LeetCode - 92. Reverse Linked List II 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/reverse-linked-list-ii/

풀이

포스트 [LeetCode] 206. Reverse Linked List와 유사한 문제이다.

차이점이 있다면 int 매개변수 m과 n을 받으며 m과 n 사이의 노드는 역순으로 표현되어야 한다. 이때, m,과 n의 범위는 을 만족한다.

m과 n 사이의 노드는 역순으로 만들어서 resultLast가 가리키는 곳에 붙여주고, m과 n사이의 노드가 아닐 때에는 단순히 resultLast 위치에 노드를 추가해주었다.

소스 코드

/**
 * 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) {
        ListNode* result = nullptr, *rev = nullptr,
            *resultLast = nullptr, *revLast = nullptr;
        int position = 0;
        for (ListNode* now = head; now != nullptr; now = now->next) {
            ++position;
            if (position >= m && position <= n) {
                ListNode* newNode = new ListNode(now->val, rev);
                if (rev == nullptr) {
                    revLast = newNode;
                }
                rev = newNode;
                if (position == n) {
                    if (resultLast != nullptr) {
                        resultLast->next = rev;
                        resultLast = revLast;
                    }
                    else {
                        result = rev;
                        resultLast = revLast;
                    }
                }
                continue;
            }

            ListNode* newNode = new ListNode(now->val);
            if (result == nullptr) {
                result = newNode;
                resultLast = newNode;
            }
            else {
                resultLast->next = newNode;
                resultLast = newNode;
            }
        }
        return result;
    }
};