【Leetcode Daily】1721交换链表中的节点

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个链表和一个数字 k，现在要把正数第 k 个节点的值和倒数第 k 个节点的值交换，求最终的链表。

思路分享

• 两个方法，交换值和交换节点，那肯定是交换值简单。双指针，间隔 k 就能找到倒数第 k 个节点，正数的更不用说，然后交换值即可。

• 交换节点的可就复杂些，找到要交换节点的前一个点，分别交换这两个点以及这两个点的 next（所以必须要哨兵节点）

  https://leetcode.cn/problems/swapping-nodes-in-a-linked-list/solutions/3853751/zuo-you-zhi-zhen-zhi-jiao-huan-jie-dian-q1qk6/

代码解答（强烈建议自行解答后再看）

• 参考题解

# 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: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 值交换
        left_k , right_k, right = head, head, head
        # 先行指针要比后空 k 位
        for _ in range(k):
            right = right.next
        
        # 下标从一开始计数
        for _ in range(k-1):
            left_k = left_k.next
        
        while right:
            right_k, right = right_k.next, right.next

        left_k.val, right_k.val = right_k.val, left_k.val

        return head