LeetCode - 24. Swap Nodes in Pairs

목차

문제 개요

난이도 - MEDIUM 사용 언어 - C++

연결 리스트가 주어지면 인접한 두 노드를 짝지어 서로 swap합니다. 이때 노드의 값을 변경하는 것은 허용되지 않고, 오직 노드의 next 포인터만 수정할 수 있습니다.

위 이미지와 같이 한 쌍의 노드를 swap합니다.

문제 - LeetCode - 24. Swap Nodes in Pairs

풀이

My Solutions(Github)

Solution

사실 난이도가 medium으로 매겨져 있지만, 단순히 두 노드의 next 포인터만 swap하면 되는 문제입니다.

흔히 프로그래밍 언어를 처음 배울 때 나오는, 두 변수를 swap하는 예제와 상당히 유사합니다.

다만 차이점이라면 순방향 연결 리스트이기 때문에 약간의 처리가 필요합니다.

while (left && right)
{
    // 일반적인 변수 swap 코드
    ListNode* tmp = right->next;

    right->next = left;
    left->next = tmp;

    // 현재 swap하는 노드의 previous 노드의 next를 연결한다.
    if (prev) prev->next = right;
    prev = left;

    // 첫 순회면 head 포인터를 업데이트한다.
    if (head == left) head = right;

    // left, right 포인터를 다음 swap할 포인터로 옮긴다.
    left = tmp;
    if (tmp) right = tmp->next;
}

실질적인 실행 코드는 단 10줄가량으로 정리됩니다. 추가 설명은 하지 않겠습니다.

제출 결과

난이도가 medium으로 매겨진 것과 다르게, 사실상 easy 난이도나 다름없었습니다.

종종 느끼지만, leetcode에서 매기는 난이도는 상당히 이상하다고 느껴질 때가 있는 것 같습니다.

class Solution {
public:
    ListNode* swapPairs(ListNode* head) 
    {
        if (!head) return nullptr;

        ListNode* prev = nullptr;
        ListNode* left = head;
        ListNode* right = head->next;

        while (left && right)
        {
            ListNode* tmp = right->next;

            right->next = left;
            left->next = tmp;

            if (prev) prev->next = right;
            prev = left;

            if (head == left) head = right;
            
            left = tmp;
            if (tmp) right = tmp->next;
        }
        
        return head;
    }
};