visual studio网站开发,百度推广的费用,wordpress 自定义二级菜单,代发视频赚钱app目录
力扣24. 两两交换链表中的节点
解析代码 力扣24. 两两交换链表中的节点
24. 两两交换链表中的节点
难度 中等
给你一个链表#xff0c;两两交换其中相邻的节点#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题#xff08;即两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。
示例 1 输入head [1,2,3,4]
输出[2,1,4,3]示例 2
输入head []
输出[]示例 3
输入head [1]
输出[1]提示
链表中节点的数目在范围 [0, 100] 内0 Node.val 100
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* swapPairs(ListNode* head) {}
}; 解析代码
递归法在下面链接讲过
Offer必备算法07_递归_五道力扣题详解由易到难-CSDN博客 迭代法就是自己画图不要吝啬定义指针直接定义四个指针在前面new一个头结点视为prev让cur和next1交换然后四个指针像后走结束条件是cur或者next1为空。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode *newHead new ListNode(0);if(head nullptr || head-next nullptr)return head;// newHead - 1 - 2 - 3// 1和2换 - cur和next1换// prev - cur - next1 - next2// cur - prev - next1 - next2ListNode *prevnewHead, *curhead, *next1head-next, *next2next1-next;while(cur next1){prev-next next1;next1-next cur;cur-next next2;prev cur;cur next2;if(cur)next1 cur-next;if(next1)next2 next1-next;}cur newHead-next;delete newHead;return cur;// 递归法// if(head nullptr || head-next nullptr)// return head;// ListNode* tmp swapPairs(head-next-next); // 把两个结点之外的看成另一部分// head-next-next head;// auto ret head-next; // 保存一下要返回的结点// head-next tmp;// return ret;}
};
