[LeetCode] 92.Reverse Linked List II - 링크드리스트 중간 구간만 뒤집는 법 (C++ 풀이)

Reverse Linked List II 문제는 단순히 연결리스트를 전체 뒤집는 것이 아니라, 특정 위치 구간만 역전시키는 알고리즘 문제입니다. 포인터 조작이 핵심이라 처음엔 헷갈릴 수 있지만, 구조를 이해하면 다른 문제에도 유용하게 쓸 수 있는 로직입니다.

 

핵심 풀이 아이디어는 다음과 같습니다.

letf 바로 뒷쪽을 prev로 설정한 다음, left바로 다음에 오는 노드를 prev 앞으로 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) {
        ListNode dummy(0);
        dummy.next = head;
        
        ListNode* prev = &dummy;
        ListNode* cur;
        ListNode* tmp;

        //prev, tmp 할당
        for(int i = 0; i < left - 1; i++){
            prev = prev->next;
        }
        cur = prev->next;
        //cur 앞의 숫자를 perv 앞으로 계속 밀어 넣기
        for(int i = 0; i < right - left; i++){
            tmp = cur->next;
            cur->next = tmp->next;
            tmp->next = prev->next;
            prev->next = tmp;
        }

        return dummy.next;
    }
};

dummy: 말그대로 더미 노드입니다. head 앞에 삽입시켜 줘, left가 1인경우에도 prev가 존재할 수 있게 해 줍니다. 저는 이 변수가 스택동적으로 생성되는 변수라서 헷갈렸는데 스택이든 힙이든 신경 쓰지 않으셔도 되고 포인터 조작 똑같이 하시면 됩니다.

cur: left위치에 있는 노드 입니다. 이 노드 앞을 계속 prev앞으로 옮길 것입니다.
prev: 시작할 때 left위치의 노드의 바로 뒤쪽입니다. left가 1인경우를 생각해야 하니 dummy가 필요한 것입니다.

tmp: cur 바로 앞의 노드입니다. 이것을 prev 앞쪽으로 보냅니다. 앞으로 보내고 나면  cur 앞의 노드로 재지정해줘야 합니다(유일하게 변경되는 포인터)

tmp를 지정 -> cur의 다음 부분을 tmp의 next로 변경 -> tmp의 next는 prev의 next로 변경(cur로 변경하는 거 아닙니다) -> 마지막으로 prev의 next는 tmp로 바꿔줍니다. 

 

이 순서가 꼬이면 포인터가 유실됩니다. prev의 넥스트를 tmp로 먼저 변경하면 tmp의 next를 prev의 next로 변경할 수 없겠죠?