(Leet Code c++)Swap Nodes in Pairs

24. Swap Nodes in Pairs

Medium

4452236Add to ListShare

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.)

 

Example 1:

Input: head = [1,2,3,4] Output: [2,1,4,3]

Example 2:

Input: head = [] Output: []

Example 3:

Input: head = [1] Output: [1]

 

Constraints:

• The number of nodes in the list is in the range [0, 100].
• 0 <= Node.val <= 100

주어진 연결 리스트에서 인접한 2개의 노드의 위치를 서로 바꿔야 한다.

 

예를 들어 1-2-3-4-5-6-7-8-9-10 라는 연결 리스트가 있다면,

2-1-4-3-6-5-8-7-10-9 로 바꿔야 한다.

 

우선 head에 있는 값을 벡터 v에 담는다.

단, 조건에 맞게 짝수번째 인덱스에 도달한다면 v 벡터 맨 뒤의 값을 잠시 빼놓은 다음(tmp에 저장),

현재 head 값을 넣고 빼놓은 값을 다시 v 맨 뒤에 push한다.

 

이후 v 벡터에 있는 값을 차례대로 연결 리스트 형태로 저장하면 된다.

/**
 * 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) {
        vector<int> v;
        int length = 1;
        ListNode * answer = new ListNode();
        ListNode * tail = answer;
        
        while(head != NULL){
            if(length % 2){
                v.push_back(head->val);
            } else{
                int tmp = v.back();
                v.pop_back();
                v.push_back(head->val);
                v.push_back(tmp);
            }
            length++;
            head = head->next;
        }
        
        for(int i = 0; i < v.size(); i++){
            tail->next = new ListNode(v[i]);
            tail = tail->next;
        }
        
        return answer->next;
    }
};