介绍

欢迎来到 LeetCode 题目每日文章！在今天的文章中，我们将探讨第1721道题目，“交换链表中的节点”。我们将深入讨论问题陈述，讨论解决问题的方法，提供解决方案的伪代码，并分析时间和空间复杂度。让我们开始吧！

问题陈述

题目要求我们给定一个链表和一个整数k，我们的任务是交换链表中从开头计数的第k个节点和从末尾计数的第k个节点。在执行交换操作后，我们需要返回更新后的链表。

约束条件

• 链表中节点的数量在1到10⁵之间。
• 链表中每个节点的值在1到100之间。

方法

为了解决这个问题，我们可以采用一个简单的方法。我们将使用两个指针，first和second，来跟踪从开头计数的第k个节点和从末尾计数的第k个节点。

• 首先，我们将在链表中将first指针向前移动k个位置。
• 接下来，我们将开始移动first和second指针，直到first指针到达链表的末尾。这将使second指针到达从末尾计数的第k个节点。
• 一旦我们确定了两端的第k个节点，我们就会交换它们的值。
• 最后，我们将返回修改后的链表。

伪代码

让我们用伪代码概述这些步骤：

function swapNodes(head, k):
    first = head
    second = head
    for i in range(k-1):
        first = first.next
    
    temp = first
    while temp.next:
        temp = temp.next
        second = second.next
    
    first.val, second.val = second.val, first.val
    return head

时间复杂度

这种方法的时间复杂度为_O(n)_，其中_n_是链表中节点的数量。我们需要遍历链表两次：一次查找从开头计数的第k个节点，另一次查找从末尾计数的第k个节点。由于我们只遍历链表一次，因此时间复杂度是线性的。

空间复杂度

我们解决方案的空间复杂度为_O(1)_。我们使用了固定量的额外空间来存储指针和临时变量。因此，空间复杂度不取决于输入大小。

完整解决方案

以下是解决问题的完整解决方案：

Python

# 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:
       
        left_node = head
        for i in range(1, k):
            left_node = left_node.next
        
       
        right_node = head
        current = left_node
        while current.next:
            current = current.next
            right_node = right_node.next
        
     
        left_node.val, right_node.val = right_node.val, left_node.val
        
        return head

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode leftNode = head, rightNode = head;
        
        for (int i = 1; i < k; i++) {
            leftNode = leftNode.next;
        }
        
        ListNode current = leftNode;
        while (current.next != null) {
            current = current.next;
            rightNode = rightNode.next;
        }
        
        int temp = leftNode.val;
        leftNode.val = rightNode.val;
        rightNode.val = temp;
        
        return head;
    }
}

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapNodes(ListNode* head, int k) {
        ListNode* leftNode = head;
        ListNode* rightNode = head;
        
        for (int i = 1; i < k; i++) {
            leftNode = leftNode->next;
        }
        
        ListNode* current = leftNode;
        while (current->next != nullptr) {
            current = current->next;
            rightNode = rightNode->next;
        }
        
        int temp = leftNode->val;
        leftNode->val = rightNode->val;
        rightNode->val = temp;
        
        return head;
    }
};

结论

在本文中，我们探讨了 LeetCode 问题1721，“交换链表中的节点”。我们解释了问题陈述，讨论了解决问题的方法，提供了解决方案的伪代码，并分析了时间和空间复杂度。我们还在Python、Java和C++中呈现了完整的解决方案。

记住，定期练习和解决各种问题是掌握编码技能的关键。因此，请保持热情，挑战自己解决更多的LeetCode问题！