1. 题目描述

给你链表的头节点 head 和一个整数 k 。
交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。

示例 1：
1721. 交换链表中的节点 - 图1

  1. 输入：head = [1,2,3,4,5], k = 2
  2. 输出：[1,4,3,2,5]

示例 2：

  1. 输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5
  2. 输出：[7,9,6,6,8,7,3,0,9,5]

示例 3：

  1. 输入：head = [1], k = 1
  2. 输出：[1]

示例 4：

  1. 输入：head = [1,2], k = 1
  2. 输出：[2,1]

示例 5：

  1. 输入：head = [1,2,3], k = 2
  2. 输出：[1,2,3]

提示：

  • 链表中节点的数目是 n
  • 1 <= k <= n <= 10

  • 0 <= Node.val <= 100

    2. 解题思路

    对于这道题目，我们可以使用快慢指针来解决，具体实现思路如下：

  • 初始化一个dummy哑结点，指向head，也就是在head之前放一个空节点，这样就避免了越界，少了一些指针为空的判断；

  • 初始化slow和fast两个快慢指针，初始时都指向哑结点dummy，并出初始化一个cur指针，用来之后保存第k个值；
  • 首先让快指针和cur移动k步，慢指针保持不动，这样此时，cur指向的就是第k个值，快慢指针之间隔着k步；
  • 让快慢指针一起走，直到快指针走到头为止，由于两者之间隔着k步，所以此时慢指针指向倒数第k个节点
  • 将此时慢指针指向的元素，也就是倒数第k个元素和cur元素，也就是第k个元素进行交换；
  • 最后返回链表头结点head即可。


复杂度分析：**

  • 时间复杂度：O(n)。其中n为链表的长度，我们需要遍历整个链表。

  • 空间复杂度：O(1)。需要额外的常数大小的辅助空间。

    3. 代码实现

    1. /**
    2. * Definition for singly-linked list.
    3. * function ListNode(val, next) {
    4. *     this.val = (val===undefined ? 0 : val)
    5. *     this.next = (next===undefined ? null : next)
    6. * }
    7. */
    8. /**
    9. * @param {ListNode} head
    10. * @param {number} k
    11. * @return {ListNode}
    12. */
    13. var swapNodes = function(head, k) {
    14.   let dummy = new ListNode(0)
    15.   dummy.next = head
    17.   let i = 0, cur = dummy
    18.   let slow = dummy, fast =dummy
    20.   while(i++ < k){
    21.       fast = fast.next
    22.       cur = cur.next
    23.   }
    25.   while(fast){
    26.       fast = fast.next
    27.       slow = slow.next
    28.   }
    30.   let temp = cur.val
    31.   cur.val = slow.val
    32.   slow.val = temp
    34.   return head
    35. };

    4. 提交结果

    image.png