难度: Medium
给你链表的头节点 head 和一个整数 k 。
交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。
示例 1：
输入：head = [1,2,3,4,5], k = 2 输出：[1,4,3,2,5]
示例 2：
输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5 输出：[7,9,6,6,8,7,3,0,9,5]
示例 3：
输入：head = [1], k = 1 输出：[1]
示例 4：
输入：head = [1,2], k = 1 输出：[2,1]
示例 5：
输入：head = [1,2,3], k = 2 输出：[1,2,3]
提示：
n1 <= k <= n <= 1050 <= Node.val <= 100运行时间: 892 ms
内存: 48.6 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapNodes(self, head: ListNode, k: int) -> ListNode:
if head is None or head.next is None:
return head
f = s = head
for _ in range(k-1):
f = f.next
p = f
f = f.next
while f:
f = f.next
s = s.next
p.val, s.val = s.val, p.val
return head
这个题解的思路是先找到正数第k个节点，用指针p记录其位置。然后用快慢指针f和s同时从头节点出发，f先走k步，接着f和s同时向后移动，直到f走到链表末尾。此时s指向倒数第k个节点。最后交换p和s指向的节点的值即可。
时间复杂度: O(n)
空间复杂度: O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapNodes(self, head: ListNode, k: int) -> ListNode:
if head is None or head.next is None:
return head
# f和s指向头节点
f = s = head
# f先走k-1步，找到正数第k个节点
for _ in range(k-1):
f = f.next
# p指针记录第k个节点的位置
p = f
# f再向后走一步
f = f.next
# f和s同时向后遍历，直到f走到链表末尾
while f:
f = f.next
s = s.next
# 交换p和s指向的节点的值
p.val, s.val = s.val, p.val
return head
在链表只有一个节点时，正数第k个节点和倒数第k个节点都是这一个节点本身。因此，交换这个节点与自身的值并不会产生任何效果，链表的状态仍然保持不变。
如果链表的长度正好是2k，那么正数第k个节点和倒数第k个节点确实指向同一个节点。在这种情况下，算法会将这个节点的值与自身交换，这与单节点的情况类似，实际上不会改变链表的状态。
这样设计的原因是为了定位到正数第k个节点和倒数第k个节点。快指针f先走k-1步是为了到达正数第k个节点，此时的f指针正好指向第k个节点。然后f再向前一步，并与慢指针s同时移动，这样可以保证当f走到链表尾部时，s指针恰好指向倒数第k个节点。如果一开始就让f和s一起走，那么无法确保f指针能正确停在正数第k个节点上，因此需要先定位f，再开始移动s。
交换节点的值相比于交换节点本身具有一些优势和劣势。优势包括操作简单，不需要调整任何节点的next指针，降低了操作复杂性和出错的可能性。劣势是这种方式只是改变了节点中的数据，而不是节点在链表中的位置。如果链表中的节点除了值外还包含其他复杂的数据结构或者引用，仅交换值可能会导致意外的副作用或错误。