528-swapping-nodes-in-a-linked-list.md

528. 交换链表中的节点 - 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]

 

提示：

• 链表中节点的数目是 n
• 1 <= k <= n <= 105
• 0 <= Node.val <= 100

thinking

1. 快慢指针

• 快指针先走 k 步，记录 k 节点值及其前节点值。
• 快慢指针一起走，直到快指针走到尾。慢指针就是倒数 k 个节点。同时记录其前一个值。
• 交换两个节点（注意当两个节点相邻时，交换的处理）

code

# 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:
        s = ListNode(next=head)
        low, fast = s, s
        pl, pf = None, None
        kn = None

        for i in range(k):
            pf, fast = fast, fast.next
        
        kn = fast

        while fast:
            fast = fast.next
            pl, low = low, low.next
        
        # swap kn and low
        if pl == kn:
            # pf, kn, low, others
            kn.next, low.next = low.next, kn
            pf.next = low
        elif pf == low:
            # pl, low, kn, others
            low.next, kn.next = kn.next, low
            pl.next = kn
        else:
            low.next, kn.next = kn.next, low.next
            pl.next, pf.next = pf.next, pl.next
        return s.next