解题思路

1. 使用链表节点进行交换：

   • 采用 虚拟头节点 (dummy) 方便处理头节点的交换情况。
   • 维护 前驱指针 (prev) 负责连接交换后的节点。
   • 设定 first 和 second 指针，分别指向当前要交换的两个相邻节点。
   • 交换 first 和 second 后，更新 prev 以继续处理后续节点。

2. 特殊情况处理：

   • 如果 sz == 0 或 sz == 1，无需交换，直接返回原链表。

时间复杂度 & 空间复杂度

• 时间复杂度：O(sz)，每个节点访问一次并进行交换。
• 空间复杂度：O(1)，只使用了额外指针，不占用额外存储空间。

Python 代码

import sys

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

def swapPairs(head):
    """ 交换链表中的相邻节点 """
    dummy = ListNode(-1)  # 创建虚拟头节点
    dummy.next = head  # 让 dummy 指向链表头部
    prev = dummy  # 前驱指针
    
    while prev.next and prev.next.next:
        first = prev.next  # 当前节点
        second = prev.next.next  # 相邻的下一个节点
        
        # 交换节点
        first.next = second.next
        second.next = first
        prev.next = second
        
        # 更新前驱指针，移动到下一组节点
        prev = first

    return dummy.next  # 返回交换后的链表头

def build_linked_list(lst):
    """ 通过列表构建链表 """
    if not lst:
        return None
    head = ListNode(lst[0])
    current = head
    for val in lst[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

def linked_list_to_list(head):
    """ 将链表转换为列表 """
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

# 读取输入
sz = int(sys.stdin.readline().strip())  # 读取链表长度
if sz == 0:
    print()  # 空链表直接换行
else:
    lst = list(map(int, sys.stdin.readline().split()))  # 读取链表数据
    head = build_linked_list(lst)  # 构建链表
    swapped_head = swapPairs(head)  # 交换相邻节点
    result = linked_list_to_list(swapped_head)  # 转换为列表
    print(" ".join(map(str, result)))

Java 代码

import java.util.*;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int sz = scanner.nextInt(); // 读取链表长度
        if (sz == 0) {
            System.out.println(); // 空链表直接换行
            return;
        }

        ListNode head = buildLinkedList(scanner, sz); // 构建链表
        head = swapPairs(head); // 交换相邻节点

        printLinkedList(head); // 输出交换后的链表
        scanner.close();
    }

    public static ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1); // 创建虚拟头节点
        dummy.next = head;
        ListNode prev = dummy;

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

            // 交换相邻节点
            first.next = second.next;
            second.next = first;
            prev.next = second;

            // 更新前驱指针
            prev = first;
        }

        return dummy.next; // 返回交换后的链表头
    }

    public static ListNode buildLinkedList(Scanner scanner, int sz) {
        ListNode head = new ListNode(scanner.nextInt());
        ListNode current = head;
        for (int i = 1; i < sz; i++) {
            current.next = new ListNode(scanner.nextInt());
            current = current.next;
        }
        return head;
    }

    public static void printLinkedList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val);
            if (current.next != null) System.out.print(" ");
            current = current.next;
        }
        System.out.println();
    }
}

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

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

ListNode* swapPairs(ListNode* head) {
    ListNode dummy(-1); // 创建虚拟头节点
    dummy.next = head;
    ListNode* prev = &dummy;

    while (prev->next && prev->next->next) {
        ListNode* first = prev->next;
        ListNode* second = prev->next->next;

        // 交换相邻节点
        first->next = second->next;
        second->next = first;
        prev->next = second;

        // 更新前驱指针
        prev = first;
    }

    return dummy.next; // 返回交换后的链表头
}

ListNode* buildLinkedList(vector<int>& lst) {
    if (lst.empty()) return nullptr;
    ListNode* head = new ListNode(lst[0]);
    ListNode* current = head;
    for (size_t i = 1; i < lst.size(); i++) {
        current->next = new ListNode(lst[i]);
        current = current->next;
    }
    return head;
}

void printLinkedList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    int sz;
    cin >> sz; // 读取链表长度

    if (sz == 0) {
        cout << endl; // 空链表直接换行
        return 0;
    }

    vector<int> lst(sz);
    for (int i = 0; i < sz; i++) {
        cin >> lst[i];
    }

    ListNode* head = buildLinkedList(lst);
    head = swapPairs(head);
    printLinkedList(head);

    return 0;
}

Leetcode 30.两两交换链表中的节点-原题链接

题目描述

给定一个链表，将相邻的节点两两交换，并返回交换后链表的头节点。
注意：不能修改节点的值，只能交换节点。

输入描述

• 第一行输入一个整数 sz（$0 \leq sz \leq 100$），表示链表的长度。
• 第二行输入 sz 个整数（$0 \leq Node.val \leq 100$），表示链表的元素，按顺序存储。

输出描述

• 输出一行，表示交换后的链表，用空格分隔节点值。
• 如果链表为空，则直接输出一个空行。

样例 1

输入

4
1 2 3 4

输出

2 1 4 3

样例 2

输入

0

输出

样例 3

输入

1
1

输出

1