1721. Swapping Nodes in a Linked List

Leetcode link

解题思路

本题要求我们找到单向链表第 k 个节点与倒数第 k 个节点交换，难点在于如何在一次遍历中找到倒数第 k 个节点

我们可以先找到第 k 个节点 n1，这个时候 head 跟 n1 的距离刚好是 k，我们用一个指针 n2 指向 head，然后 n1 与 n2 同时往后遍历链表，这样只要 n1 找到了链表的尾节点， n2 就恰巧是倒数第 k 个节点了。

C++

class Solution {
 public:
  ListNode* swapNodes(ListNode* head, int k) {
    ListNode *n1 = head, *n2 = head, *n_kth;

    while (--k > 0) {
      n1 = n1->next;
    }
    n_kth = n1;

    while (n1->next != NULL) {
      n2 = n2->next;
      n1 = n1->next;
    }
    swap(n_kth->val, n2->val);
    return head;
  }
};

Javascript

var swapNodes = function(head, k) {
    let n1 = head, n2 = head, n_kth;
    while (--k > 0) {
      n1 = n1.next;
    }
    n_kth = n1;
    while (n1.next != null) {
      n2 = n2.next;
      n1 = n1.next;
    }
    [n_kth.val, n2.val] = [n2.val, n_kth.val];
    return head;
};