24. 两两交换链表中的节点

🟠   🔖  递归 链表  🔗 力扣 LeetCode

题目

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4]

Output: [2,1,4,3]

Example 2:

Input: head = []

Output: []

Example 3:

Input: head = [1]

Output: [1]

Constraints:

• The number of nodes in the list is in the range [0, 100].
• 0 <= Node.val <= 100

题目大意

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

解题思路

思路一：迭代法

1. 使用一个虚拟头节点 res 作为新链表的头，避免处理头节点时的边界问题；
2. 初始化 prev 指针指向虚拟头节点；
3. 使用 prev 指针来遍历链表，每次交换相邻的节点 prev.next 和 prev.next.next，并更新 prev 指针，使其指向交换后的第二个节点；
4. 遍历的终止条件是：prev.next 或 prev.next.next 不存在了，即剩余节点不足两个；
5. 返回结果；

---

思路二：递归法

1. 递归终止条件：如果链表为空或只有一个节点，则返回原链表，因为没有节点可交换；
2. 交换节点：交换当前节点对，并将交换后的链表头设置为 second，递归处理剩下的链表 rest；
3. 返回新头节点：返回新的链表头 second；

代码

迭代法

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
	// 构造虚拟头节点
	let res = new ListNode(0, head);
	let prev = res;

	// 遍历链表
	while (prev.next && prev.next.next) {
		// 交换前两个节点
		let cur = prev.next;
		let temp = cur.next;
		cur.next = temp.next;
		prev.next = temp;
		temp.next = cur;
		prev = cur;
	}
	return res.next;
};

递归法

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
	// 如果链表为空或只有一个节点，不需要交换
	if (!head || !head.next) {
		return head;
	}

	// 交换前两个节点
	let first = head;
	let second = head.next;
	let rest = second.next;

	// 递归处理剩下的链表
	second.next = first;
	first.next = swapPairs(rest);

	// 返回新头节点
	return second;
};

相关题目

题号	标题	题解	标签	难度
25	K 个一组翻转链表	[✓]	递归 链表
1721	交换链表中的节点		链表 双指针