LeetCode第二十四题：两两交换链表中的节点

admin
学习
2024-03-20
64热度
0评论

题目来源：LeetCode第二十四题

1.题目描述

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

示例 1：

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

输出：[2,1,4,3]

提示：

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

2.解题思路

解法一：递归法

描述：如果链表为空（head == NULL）或者链表中仅有一个节点（head->next == NULL），则没有足够的节点进行交换，直接返回head。若链表中至少有两个节点，记当前节点为head，其后继节点为head->next先保存head->next为newHead，因为在交换后，newHead将成为新的头节点。对head->next->next（即剩余部分的头节点）进行递归调用，返回值将是交换后剩余部分的新头节点。将head->next指向这个返回值。将newHead->next指向head，完成当前对的节点交换。返回newHead，作为整个链表的新头节点。递归地对链表的剩余部分进行相同的交换操作，直到链表末尾。
时间复杂度：O(N)。其中N是链表中的节点数。
空间复杂度：O(N)。最坏情况下，递归的深度等于链表的长度。
参考代码：

java版：

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 递归的基本情况，如果链表为空或只有一个节点，直接返回头节点
        if (head == null || head.next == null) {
            return head;
        }
        // 记录第二个节点，这将是交换后的新头节点
        // 例如1->2->3->4
        // ....↑..↑
        // ..head.newHead
        ListNode newHead = head.next;
        // 将第一个节点的下一个指向递归调用的结果
        // 1->swapPairs(3->4)
        head.next = swapPairs(newHead.next);
        // 将第二个节点的下一个指向第一个节点，完成交换
        // 2->1->swapPairs(3->4)
        newHead.next = head;
        // 返回新的头节点
        return newHead;
    }
}

C++版：

class Solution {
public:
	ListNode* swapPairs(ListNode* head) {
		// 递归的基本情况，如果链表为空或只有一个节点，直接返回头节点
		if (head == nullptr || head->next == nullptr) {
			return head;
		}
		// 记录第二个节点，这将是交换后的新头节点
		// 例如1->2->3->4
		// ....↑..↑
		// ..head.newHead
		// ..head.newHead
		ListNode* newHead = head->next;
		// 将第一个节点的下一个指向递归调用的结果
		// 1->swapPairs(3->4)
		head->next = swapPairs(newHead->next);
		// 将第二个节点的下一个指向第一个节点，完成交换
		// 2->1->swapPairs(3->4)
		newHead->next = head;
		// 返回新的头节点
		return newHead;
	}
};

C版：

// 递归交换链表中的节点
struct ListNode* swapPairs(struct ListNode* head) {
	// 基本情况：如果链表为空或只有一个节点，直接返回head
	if (head == NULL || head->next == NULL) {
		return head;
	}

	// 保存第二个节点，它将成为新的头节点
	struct ListNode* newHead = head->next;
	// 递归调用，处理从第三个节点开始的链表部分
	// 并将第一个节点的next指向递归调用的结果
	head->next = swapPairs(newHead->next);
	// 将新头节点的next指向第一个节点，完成这一对的交换
	newHead->next = head;

	// 返回新的头节点
	return newHead;
}

解法二：迭代法

描述：首先，创建一个虚拟的头节点（dummy head），其next指针指向链表的实际头节点。这一步是为了简化头节点交换的逻辑，使头节点和其他节点的处理方式一致。：使用两个指针prev和curr，其中prev初始时指向虚拟头节点，而curr指向链表的第一个实际节点。在链表上迭代，每次迭代中，检查curr及其后继节点（curr->next）是否存在。如果都存在，则进行以下操作：将curr指向的节点与其后继节点交换。更新prev指针指向交换后的第二个节点。移动curr指针到下一对待交换的节点上。继续迭代，直到curr或curr->next为NULL，即没有更多的节点对可以交换。交换完成后，返回虚拟头节点的next指针，即新的头节点。
时间复杂度：O(N)。其中N是链表中的节点数。
空间复杂度：O(1)。
参考代码：

java版：

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 创建一个虚拟头节点，简化边界条件的处理
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // prev是将要交换两个节点的前一个节点
        ListNode prev = dummy;

        // 遍历链表直到当前节点或当前节点的下一个节点为空
        // 因为需要两个节点进行交换，所以当链表剩余节点小于2个时停止遍历
        while (prev.next != null && prev.next.next != null) {
            // first是当前要交换的第一个节点
            ListNode first = prev.next;
            // second是当前要交换的第二个节点
            ListNode second = first.next;
            // 下面三步完成两个节点的交换
            // 第一步：将prev的next指向second，从而跳过first
            prev.next = second;
            // 第二步：更新first的next为next的下一个节点，断开first与next的连接
            first.next = second.next;
            // 第三步：将second的next指向first，完成交换
            second.next = first;

            // 为下一对交换更新prev节点，现在first是交换后的第二个节点,也就是将要交换两个节点的前一个节点
            prev = first;
        }

        return dummy.next;
    }
}

C++版：

class Solution {
public:
	ListNode* swapPairs(ListNode* head) {
		// 创建一个虚拟头节点，简化边界条件的处理
		ListNode* dummy = new ListNode(0);
		dummy->next = head;

		// prev是将要交换两个节点的前一个节点
		ListNode* prev = dummy;

		// 遍历链表直到当前节点或当前节点的下一个节点为空
		// 因为需要两个节点进行交换，所以当链表剩余节点小于2个时停止遍历
		while (prev->next != nullptr && prev->next->next != nullptr) {
			// first是当前要交换的第一个节点
			ListNode* first = prev->next;
			// second是当前要交换的第二个节点
			ListNode* second = first->next;

			// 下面三步完成两个节点的交换
			// 第一步：将prev的next指向second，从而跳过first
			prev->next = second;
			// 第二步：更新first的next为next的下一个节点，断开first与next的连接
			first->next = second->next;
			// 第三步：将second的next指向first，完成交换
			second->next = first;

			// 为下一对交换更新prev节点，现在first是交换后的第二个节点,也就是将要交换两个节点的前一个节点
			prev = first;
		}
		return dummy->next;
	}
};

C版：

// 交换链表中两两相邻的节点
struct ListNode* swapPairs(struct ListNode* head) {
	// 使用虚拟头节点简化头节点交换的处理
	struct ListNode dummy;
	dummy.next = head;
	struct ListNode* prev = &dummy;

	// 当存在至少两个未处理的节点时执行循环
	while (prev->next != NULL && prev->next->next != NULL) {
		struct ListNode* first = prev->next;      // 第一个交换节点
		struct ListNode* second = first->next;    // 第二个交换节点

		// 执行节点交换
		first->next = second->next;
		second->next = first;
		prev->next = second;

		// 移动prev指针到下一对待交换节点的前一个节点
		prev = first;
	}

	return dummy.next;
}