1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode ptr = head;
        for (int i = 0; i < k - 1; i++) {
            ptr = ptr.next;
        }
        ListNode kthNode = ptr;
        ListNode lastKthNode = head;
        while (ptr.next != null) {
            ptr = ptr.next;
            lastKthNode = lastKthNode.next;
        }
        int temp = kthNode.val;
        kthNode.val = lastKthNode.val;
        lastKthNode.val = temp;
        return head;
    }
}

一个pass走到位. 我们让ptr先走k - 1步, 走到第k个node. 然后再引入一个ptr2从head开始, ptr走一步, ptr2也走一步. 当ptr走到最后一个node的时候, ptr2在的位置就是倒数第k个. 简单的几何关系, 对称一下就知道了.

时间复杂度: O(n)
空间复杂度: O(1)