[C++]LeetCode:109 Swap Nodes in Pairs(隣接ノードの位置を交換)

タイトル:
Given a linked list, swap every two adjacent nodes and return its head.
For example, Given  1->2->3->4 , you should return the list as  2->1->4->3 .
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
考え方:
挿入法を用いて,2つのノードを交換する.preノードを維持し、挿入した前のノードを表します.挿入するノードを表すcurノードを維持します.仮想ヘッダノードdummyheadを同時に構築し、チェーンテーブルのヘッダノードを維持します.
Attention:
1.チェーンテーブルが空の場合、またはノードが1つしかない場合は、チェーンテーブルに戻ります.

if(head == NULL || head->next == NULL) return head;

2.3つのノードを維持します.

ListNode* dummyhead = new ListNode(0);
dummyhead->next = head;
ListNode* cur = head;
ListNode* pre = dummyhead;

3.注意cur自体が最後のノードを指している場合も、処理を行わないと判断する.

while(cur != NULL && cur->next != NULL)

複雑度:O(N)
AC Code:

/**
 * 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* dummyhead = new ListNode(0);
        dummyhead->next = head;
        ListNode* cur = head;
        ListNode* pre = dummyhead;
        
        if(head == NULL || head->next == NULL) return head;
        while(cur != NULL && cur->next != NULL)
        {
            cur = cur->next;
            ListNode* tmp = cur->next;    //            
            cur->next = pre->next;        // cur    
            pre->next = cur;              
            pre = cur->next;              //  pre        
            cur->next->next = tmp;        //                   
            cur = tmp;                    //  cur  
        }
        return dummyhead->next;
    }
};