两两交换链表中的节点（24）

题目

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例

输入：head = [1,2,3,4] 输出：[2,1,4,3]

输入：head = [] 输出：[]

输入：head = [1] 输出：[1]

提示

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

算法

迭代

设立哨兵节点sentinel，新建指针sentinelNode指向哨兵节点，指针firstNode指向sentinelNode.next，指针nextNode指向sentinelNode.next.next.next，将节点重新按照sentinelNode->sentinelNode.next.next->firstNode->nextNode指向建立关系，然后每次以两个节点为一个整体向前移动，每次移动都需要确保firstNode和firstNode.next存在，最后结果返回sentinel.next

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const swapPairs = (head) => {
	if (!head || !head.next) return head;
	let sentinel = new ListNode();
	let sentinelNode = sentinel;
	sentinel.next = head;
	while (head && head.next) {
		let firstNode = head;
		let nextNode = head.next.next;
		sentinelNode.next = head.next;
		sentinelNode.next.next = firstNode;
		firstNode.next = nextNode;
		head = nextNode;
		sentinelNode = firstNode;
	}
	return sentinel.next;
};

递归

递归结束的条件：当前节点head或者head.next不存在的时候 递归返回的结果：当前递归中的头节点newHead 递归传入的参数：每次传入下一个递归的参数是head.next.next（即下一个递归片段的开始节点）， 递归中的操作：以两个相邻节点为一个整体（即head和head.next），将head.next设为newHead，将head指向内层递归返回出来的新头部，将newHead.next指向head，然后返回这个newHead作为新头部返回出去

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const swapPairs = (head) => {
	if (!head || !head.next) return head;
	let newHead = head.next;
	head.next = swapPairs(head.next.next);
	newHead.next = head;
	return newHead;
};