1721. Swapping Nodes in a Linked List - Medium

前往題目

想法

• 循環一次就能找到第一個目標，以及list的長度加以利用

思路

寫出來了但還有我認為再更聰明一點的做法

我的解法：

1. 走訪list找到第一個目標以及長度
2. 利用長度再計算需要走多少步到目標，再次走訪
3. 交換數值

更為聰明的解法：

1. 走k步到達第一個目標
2. 再一個指針cur從頭開始，與剛剛的第一個目標指針一起往右走訪直到最後，這時cur指針就會在第二個目標上
3. 交換

Code

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode first = head, sec = head, cur = head;
        int len = 0;
        int count = k - 1;
        // Find the first and the length
        while (cur != null) {
            if (count == 0) first = cur;
            ++len;
            --count;
            cur = cur.next;
        }

        count = len - k;
        cur = head;
        // Find the sec node
        while (cur != null) {
            if (count == 0) sec = cur;
            --count;
            // Move the pointer
            cur = cur.next;
        }

        // Swap
        int val = first.val;
        first.val = sec.val;
        sec.val = val;

        return head;
    }
}

更聰明的解法