⭐ 题目日期：

百度 - 2024/12/2，滴滴 - 2024/10/25，百度 - 2024/10/12

🌳 题目描述：

两两交换链表中的节点：在不修改节点内部的值的情况下，两两交换其中相邻的节点，并返回交换后链表的头节点。（注意：是交换节点 不是改变值）

示例 1：
输入：head = [1, 3, 5, 7]
输出：[3, 1, 7, 5]

解释图例：

🕵🏽‍♂️ 面试评估：

这道题考察候选人是否通过循环遍历链表节点来实现这一目标，重点是如何通过调整指针来完成节点交换，而不需要修改节点值。

🧗难度系数：

⭐️ ⭐️

📝思路分析：

首先我们需要创建一个虚拟头节点，让它指向链表的头节点，这样做可以简化边界处理，随后设置 cur 指针用于遍历链表。

在遍历过程中，我们需要先检查 cur.next 和 cur.next.next 是否为 null，以此来保证至少有一对节点可以交换。

接着用 first 和 second 来指向第一个要交换的节点和第二个要交换的节点，随后执行交换操作。交换之后，更新 cur 指针为 first，等待下一轮交换之后将其指向交换好的节点。

💻代码(Java、Python、C++)：

Java

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode DummyNode = new ListNode(0);
        DummyNode.next = head;
        ListNode cur = DummyNode;

        while (cur.next != null && cur.next.next != null) {
            ListNode first = cur.next;
            ListNode second = cur.next.next;

            first.next = second.next;
            second.next = first;
            cur.next = second;

            cur = first;
        }

        return DummyNode.next;
    }
}

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummy_node = ListNode(0)
        dummy_node.next = head
        cur = dummy_node

        while cur.next is not None and cur.next.next is not None:
            first = cur.next
            second = cur.next.next

            first.next = second.next
            second.next = first
            cur.next = second
            cur = first

        return dummy_node.next

C++

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyNode = new ListNode(0);
        dummyNode->next = head;
        ListNode* cur = dummyNode;

        while (cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* first = cur->next;
            ListNode* second = cur->next->next;

            first->next = second->next;
            second->next = first;
            cur->next = second;

            cur = first;
        }

        return dummyNode->next;
    }
};

🚵🏻复杂度分析：

• 时间复杂度：O(n)，其中 n 为链表中节点的数量。每个节点最多被访问一次。
• 空间复杂度：O(1)，只使用了常数空间来存储指针。

🔬在线评测(Online Judge):

题目链接