[LeetCode] 24. Swap Nodes in Pairs

https://leetcode.com/problems/swap-nodes-in-pairs/description/

Swap Nodes in Pairs - LeetCode

문제 유형 : 연결 리스트

문제 난이도 : Medium

 

문제

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

 

주어진 연결리스트에서 모든 두 쌍의 인접한 노드를 바꿔라. 노드의 값만 바꾸지 말고 노드 자체를 바꿔야 한다.

 

 

풀이

그냥 쭉 돌면서 바꾸면 될 거 같지만, 강력한 기법이 하나 있다.

바로 head의 앞에 더미 노드를 붙이는 방법이다.

더미 노드를 붙임으로서 반복문마다 prev가 nullptr인지 확인할 필요가 없고, 코드가 훨씬 간결해진다.

 

 

 

코드(C++)

/**
 * 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 == nullptr || head->next == nullptr) {
            return head;
        }
    
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
    
        ListNode* prev = dummy;
        ListNode* current = head;
    
        while (current != nullptr && current->next != nullptr) {
            ListNode* node1 = current;
            ListNode* node2 = current->next;
        
			//노드1과 노드2 바꾸기
            prev->next = node2;
            node1->next = node2->next;
            node2->next = node1;
        
            //앞으로 나아가기
            prev = node1;
            current = node1->next;
        }
    
        ListNode* newHead = dummy->next;
        delete dummy;
    
        return newHead;
    }

};