Q1721-交换链表中的节点-中等-链表

1721. 交换链表中的节点

Question

给你链表的头节点 head 和一个整数 k 。

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

Example 1:

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

Example 2:

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

Example 3:

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

提示：

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

Approach 1: 遍历搜索（超时）

自己思考没想出什么特别的计算手段，就想到遍历链表找到前k和后k个结点，然后进行交换

class Solution:
    def swapNodes(self, head: ListNode, k: int) -> ListNode:
        # 找前k-1个点
        L=head
        num=0
        while L:
            num+=1
            if num == k-1: # 找到前k-1个结点
                FK=L
            L=L.next
        # 找后k+1个结点
        k=num-k
        num=0
        ans=L=head # 保证ans和L相同地址
        while L:
            num+=1
            if num == k:
                LK=L
                break
            L=L.next
        # 交换
        FK2=FK.next
        FK3=FK.next.next
        LK2=LK.next
        LK3=LK.next.next

        FK.next=LK2
        LK2.next=FK3
        LK.next=FK2
        FK2.next=LK3

        return listNodeToString(ans)

复杂度分析

• 时间复杂度：O(n+q)，其中 n 是链表的节点数量，p是倒数第k个结点是链表的第p个结点。
• 空间复杂度：O(1)，增加了常数个指针。

Approach 2: 快慢指针

快慢指针用法挺多 1.n等分 2.检测有无环 3.从后数第几个

class Solution:
    def swapNodes1(self, head: ListNode, k: int) -> ListNode:
        fast = head
        while k - 1 != 0: # 1 2 3 4 5 6 7  k=3 往后移2步到3
            fast = fast.next
            k -= 1
        L = fast # L = 3
        slow = head
        while fast.next: # slow = 5, fast = 7
            fast = fast.next
            slow = slow.next
        R = slow # R = 5

        L.val,R.val = R.val,L.val #3 和 5 的val 交换
        return head

复杂度分析

• 时间复杂度：O(n)。其中n为链表的长度。
• 空间复杂度：O(1)。需要额外的常数大小的辅助空间。