[leetcode] 24. Swap Nodes in Pairs

문제

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list's nodes, only nodes itself may be changed.

 

풀이

기본적인 list 구현문제이다.

적당한 list 연산을 이용해서, 위의 list를 아래와 같이 변형시켜주는 계산을 진행한다.

Time Complexity : $O(n)$

 

풀이

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* prev = new ListNode(0);
        prev->next=head;
        for(ListNode *it=prev; it!=NULL;)
        {
            if(it->next==NULL || it->next->next==NULL) break;
            ListNode *temp=it->next;
            it->next=it->next->next;
            temp->next = it->next->next;
            it->next->next=temp;
            it=temp;
        }
        return prev->next;
    }
};