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

一、问题描述

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

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

二、方案一：迭代法

1、思路

使用迭代法来两两交换链表中的节点。

• 定义虚拟头结点，这样会方便很多，要不然每次针对头结点特殊处理（没有前一个指针指向头结点的场景）
• 通过下面三个步骤完成相邻节点的交换，然后指针向后移动2位，重复上面的过程

2、代码实现

func swapPairs(head *ListNode) *ListNode {
	var dummy *ListNode = &ListNode{Next: head}
	var cur *ListNode = dummy
	for cur.Next != nil && cur.Next.Next != nil {
		// 保存第一个节点
		tmp1 := cur.Next
		// 保存后置节点
		tmp2 := cur.Next.Next.Next

		/* 第2个节点和第1个节点交换 */

		// 步骤一：前置节点指向第2个节点
		cur.Next = cur.Next.Next
		// 步骤2：第2个节点指向第1个节点
		cur.Next.Next = tmp1
		// 步骤3：第1个节点指向后置节点
		tmp1.Next = tmp2

		cur = cur.Next.Next // cur移动两位，准备下一轮交换
	}

	return dummy.Next
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。我们需要遍历整个链表一次。
• 空间复杂度：O(1)，不需要额外的空间。

三、方案二：递归法

1、思路

使用递归法来两两交换链表中的节点。递归法的基本思路是：

• 设置当前节点的下一个节点的指针指向当前节点。
• 递归地交换剩余的链表。
• 将当前节点的指针指向新的头节点。

2、代码实现

func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    // 创建一个节点指针类型保存头结点下一个节点
    newHead := head.Next
    // 更改头结点，并将头结点的next指针指向这个更改过的list
    head.Next = swapPairs(newHead.Next)
    // 将新的头结点的next指针指向老的头节点
    newHead.Next = head
    return newHead
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。我们需要遍历整个链表一次。
• 空间复杂度：O(n)，递归调用栈的空间。

四、总结

方案	时间复杂度	空间复杂度
迭代法	O(n)	O(1)
递归法	O(n)	O(n)

迭代法在空间复杂度上更优，而递归法在代码结构上更简洁。选择哪种方法取决于具体的使用场景和个人偏好。