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]

提示：

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

解题思路

解题思路

这道题要求交换链表中正数第 k 个节点和倒数第 k 个节点的值。我们可以采用多种方法来解决：

方法一：双指针法（推荐）

使用双指针技巧，一次遍历找到两个目标节点：

  1. 先让第一个指针走 k-1 步，到达正数第 k 个节点
  2. 保存这个节点，然后让两个指针同时前进
  3. 当第一个指针到达末尾时，第二个指针正好在倒数第 k 个节点

方法二：两次遍历法

  1. 第一次遍历计算链表长度 n
  2. 第二次遍历找到正数第 k 个和第 (n-k+1) 个节点（即倒数第 k 个）
  3. 交换两个节点的值

方法三：转换为数组

将链表转换为数组，利用索引直接访问和交换，然后重建链表。但这种方法空间复杂度较高。

双指针法最为优雅，只需一次遍历，时间复杂度 O(n)，空间复杂度 O(1)。

代码实现

class Solution {
public:
    ListNode* swapNodes(ListNode* head, int k) {
        ListNode* first = head;
        ListNode* second = head;
        ListNode* kth = nullptr;
        
        // 找到正数第k个节点
        for (int i = 1; i < k; i++) {
            first = first->next;
        }
        kth = first;
        
        // 双指针找到倒数第k个节点
        while (first->next) {
            first = first->next;
            second = second->next;
        }
        
        // 交换值
        swap(kth->val, second->val);
        
        return head;
    }
};

class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        first = second = head
        
        # 找到正数第k个节点
        for _ in range(k - 1):
            first = first.next
        kth = first
        
        # 双指针找到倒数第k个节点
        while first.next:
            first = first.next
            second = second.next
        
        # 交换值
        kth.val, second.val = second.val, kth.val
        
        return head

public class Solution {
    public ListNode SwapNodes(ListNode head, int k) {
        ListNode first = head;
        ListNode second = head;
        ListNode kth = null;
        
        // 找到正数第k个节点
        for (int i = 1; i < k; i++) {
            first = first.next;
        }
        kth = first;
        
        // 双指针找到倒数第k个节点
        while (first.next != null) {
            first = first.next;
            second = second.next;
        }
        
        // 交换值
        int temp = kth.val;
        kth.val = second.val;
        second.val = temp;
        
        return head;
    }
}

var swapNodes = function(head, k) {
    let first = head;
    let second = head;
    let kth = null;
    
    // 找到正数第k个节点
    for (let i = 1; i < k; i++) {
        first = first.next;
    }
    kth = first;
    
    // 双指针找到倒数第k个节点
    while (first.next) {
        first = first.next;
        second = second.next;
    }
    
    // 交换值
    [kth.val, second.val] = [second.val, kth.val];
    
    return head;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型双指针法两次遍历法数组转换法
时间复杂度O(n)O(n)O(n)
空间复杂度O(1)O(1)O(n)

说明：

  • 时间复杂度：所有方法都需要遍历链表，所以都是 O(n)
  • 空间复杂度：双指针法和两次遍历法只使用常数额外空间，数组转换法需要 O(n) 的额外空间存储数组

相关题目