网站地区分站系统,重庆网站建设总结与体会,wordpress tag 优化,徐州房产网24. 两两交换链表中的节点
Leetcode 24 给你一个链表#xff0c;两两交换其中相邻的节点#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题#xff08;即#xff0c;只能进行节点交换#xff09;。
递归解法
// 注意#xff1a;cpp …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; }
};
