1721. Swapping Nodes in a Linked List

題目連結: 1721. Swapping Nodes in a Linked List

題意

給定一個 linked list 以及一個數字 k，將從頭數第 k 個節點與倒數第 k 個節點交換。

• 1-indexed

限制

• The number of nodes in the list is n.
• 1 <= k <= n <= 10^5
• 0 <= Node.val <= 100

思考

• 建立一個指標 fast 從 head 開始向前移動 k - 1 次，取得第 k 個節點，並用另一個變數 first 記住這個位置。
• 建立另一個指標 slow，同樣從 head 開始，與 fast 同步向前移動，直到 fast 抵達串列末端。
  • 由於 fast 已經先移動了 k - 1 次，所以 slow 與 fast 之間相差 k - 1 個節點。
  • 當 fast 到達串列末端時，slow 便會停在倒數第 k 個節點。
• 交換 first->val 與 slow->val 即可完成需求。

Solution

/**
 * 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* swapNodes(ListNode* head, int k) {
        k -= 1;
        auto fast = head;
        while (k--) {
            fast = fast->next;
        }
        auto first = fast;
        auto slow = head;
        while (fast->next) {
            fast = fast->next;
            slow = slow->next;
        }
        swap(first->val, slow->val);
        return head;
    }
};

複雜度計算

時間複雜度
在上述過程中，我們只需要依序遍歷連結串列一次，因此整體時間複雜度為 O(n)，其中 n 為串列長度。

空間複雜度
除了幾個指標外，並未額外使用任何額外儲存空間，因此空間複雜度為 O(1)。