题目概览
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]输出：[2,1,4,3]
示例 2：
输入：head = []输出：[]
示例 3：
输入：head = [1]输出：[1]
提示：
- 链表中节点的数目在范围
[0, 100]内 0 <= Node.val <= 100
来源：24. 两两交换链表中的节点 - 力扣（LeetCode）
解题分析
方法一：模拟 + 迭代
令相邻的两个节点为 a，b，交换的过程就是：
- a 的前一个节点指向 b
- b 指向 a
- a 指向 b 的后一个节点
记录前一个节点，然后遍历链表进行交换即可。
时间复杂度：O(n)
空间复杂度：O(1)
/** * 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 swapPairs(ListNode head) { if (head == null || head.next == null) { return head; } ListNode node = head, pre = new ListNode(), result = pre; while(node != null && node.next != null) { pre.next = node.next; pre = node; ListNode temp = node.next.next; node.next.next = node; node.next = temp; node = node.next; } return result.next; } }方法二：模拟 + 递归
参考一，每次调用该方法进行交换，然后 a 指针指向下一个交换的头节点（再调用该方法）。
时间复杂度：O(n)
空间复杂度：O(n)
/** * 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 swapPairs(ListNode head) { if (head == null || head.next == null) { return head; } ListNode result = head.next; // 交换 ListNode temp = head.next.next; head.next.next = head; head.next = swapPairs(temp); return result; } }
