leetcode : Swap Nodes in Pairs

runtime 0 ms, beats 100% of cpp submissions
O(n) solution with explanation

tags: linked list, pointer

🔗 link

Swap Nodes in Pairs

📖 description

給定一個 linked list ，將相鄰的兩個點翻轉。

ex.
    1 -> 2 -> 3 -> 4

    2 -> 1 -> 4 -> 3

    1、2互換，3、4互換

🧠 solution

根據題意模擬即可，使用兩個 pointer 分別指向需要互換的兩個點，互換完後再向後移動兩格。

⏳ time complexity

遍歷一次 list ，時間複雜度 O(n)
總時間複雜度 O(n)

📝 code

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==nullptr || head->next==nullptr){ // 確保有至少兩個點
            return head;
        }
        ListNode* f = head;         // first pointer
        ListNode* s = head->next;   // second pointer
        ListNode* ans = f;
        while(s!=nullptr){
            swap(f->val,s->val);    // 交換數值
            f=s->next;
            if(f==nullptr) break;
            s=s->next->next;
        }
        return ans;
    }
};