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 次，得到第一個節點，並用另一個變數 first 記住這個位子

• 建立另一個 slow ，從 head 開始，與 fast 平行向前移動直到 fast 抵達 list 末端

  • 由於 fast 已經先移動了 k-1 次， slow 與 fast 就會相差 k - 1 個節點

  • 由於平行移動，距離不變，等到 fast 抵達末端， slow 就會距離末端 k - 1

• 交換 first 與 slow

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;
    }
};