当前位置：首页 > news >正文

递归-迭代

news 2025/6/29 17:28:38

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

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

递归解法

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译。
// 本代码的正确性已通过力扣验证，如有疑问，可以对照 java 代码查看。class Solution {
public: // Ensure that swapPairs is public// 定义：输入以 head 开头的单链表，将这个单链表中的每两个元素翻转，// 返回翻转后的链表头结点ListNode* swapPairs(ListNode* head) {if (head == nullptr || head->next == nullptr) {return head;}ListNode* first = head;ListNode* second = head->next;ListNode* others = head->next->next;// 先把前两个元素翻转second->next = first;// 利用递归定义，将剩下的链表节点两两翻转，接到后面first->next = swapPairs(others);// 现在整个链表都成功翻转了，返回新的头结点return second;}
};

迭代解法

// 虚节点的重要性

// 方法二：迭代 
class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* temp = dummyHead;while (temp->next != nullptr && temp->next->next != nullptr) {ListNode* node1 = temp->next;ListNode* node2 = temp->next->next;temp->next = node2;node1->next = node2->next;node2->next = node1;temp = node1;}ListNode* ans = dummyHead->next;delete dummyHead;return ans;}
};

如果不加哨兵节点，则需要对头节点进行特殊处理：

// 不加dummy 节点的版本
class Solution {
public:ListNode* swapPairs(ListNode* head) {if (head == nullptr || head->next == nullptr) {return head;}ListNode* pNode = head;head = head->next;// 对头节点的交换需要特殊处理，因为头节点的前一个节点为空   ListNode* node1 = pNode;ListNode* node2 = pNode->next;    // 交换节点node1->next = node2->next;node2->next = node1;pNode = node1;while (pNode->next != nullptr && pNode->next->next != nullptr) {ListNode* node1 = pNode->next;ListNode* node2 = pNode->next->next;    // 交换节点pNode->next = node2;node1->next = node2->next;node2->next = node1;pNode = node1;}return head;  }
};