[ leetcode ] 24. Swap Nodes in Pairs

해당 문제는 Recursion을 사용하여 재귀적으로 같은 문제를 해결할 수 있는지를 판단하는 문제로 보였습니다.

Linked List가 주어졌을 때, 서로 인접한 두개의 노드의 순서가 변경된 결과를 반환하는 문제입니다.

ex) 1 -> 2 -> 3 -> 4

      2 -> 1 -> 4 -> 3

작은 단위로 쪼개보면 인접한 두개의 노드가 서로 자리를 바꾸는 연산이 반복해서 일어나므로 재귀적으로 해결한다면 다음과 같은 코드로 풀이할 수 있습니다.

첫 번째 노드가 current, 두 번째 노드가 next라고 한다면 결과적으로 next->next는 current를 가리키고, current->next는 다음 두 노드의 변경된 첫 번째 노드를 가리켜야 합니다.

다음 두 노드의 결과는 swapPairs(next->next)가 되므로 아래 코드가 나오게 됩니다.

/**
 * 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* swapPairs(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;

        ListNode* current = head;
        ListNode* next = current->next;
        
        current->next = swapPairs(next->next);
        next->next = current;
        
        return next;
	}
};