门户网站建设哪家好,咸阳网站建设费用,制作wordpress页面模板下载,韩国免费行情网站的推荐理由LeetCode.24两两交换链表中的节点 1.问题描述2.解题思路3.代码 1.问题描述
给你一个链表#xff0c;两两交换其中相邻的节点#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题#xff08;即#xff0c;只能进行节点交换#xff09;。
示… LeetCode.24两两交换链表中的节点 1.问题描述2.解题思路3.代码 1.问题描述
给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。
示例 1 输入head [1,2,3,4]
输出[2,1,4,3]示例 2
输入head []
输出[]示例 3
输入head [1]
输出[1]提示
链表中节点的数目在范围 [0, 100] 内0 Node.val 100
2.解题思路
同样设置虚拟头结点接下来就是交换相邻两个元素了此时一定要画图不画图操作多个指针很容易乱而且要操作的先后顺序
初始时cur指向虚拟头结点然后进行如下三步 操作之后链表如下 看这个可能就更直观一些了 切记要记录临时节点因为如果不记录某一步操作之后将会影响接下来的操作。
ListNode* tmp cur-next; // 记录临时节点
ListNode* tmp1 cur-next-next-next; // 记录临时节点3.代码
C
#include iostream
#include vector
using namespace std;// 定义链表节点结构
struct ListNode {int val; // 节点存储的值ListNode* next; // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {} // 构造函数
};class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummyHead new ListNode(0); // 设置一个虚拟头结点dummyHead-next head; // 将虚拟头结点指向head这样方便后面做删除操作ListNode* cur dummyHead;while(cur-next ! nullptr cur-next-next ! nullptr) {ListNode* tmp cur-next; // 记录临时节点ListNode* tmp1 cur-next-next-next; // 记录临时节点cur-next cur-next-next; // 步骤一cur-next-next tmp; // 步骤二cur-next-next-next tmp1; // 步骤三cur cur-next-next; // cur移动两位准备下一轮交换}return dummyHead-next;}
};// 根据一个整数数组创建链表
ListNode* createList(vectorint nums) {ListNode* head NULL;ListNode* current NULL;for (int i 0; i nums.size(); i) {if (head NULL) {head new ListNode(nums[i]);current head;} else {current-next new ListNode(nums[i]);current current-next;}}return head;
}// 打印链表中的元素
void printList(ListNode* head) {ListNode* cur head; // 当前节点指针while(cur) {cout cur-val ; // 打印当前节点值cur cur-next; // 移动到下一个节点}cout endl; // 打印换行符
}// 主函数
int main() {vectorint nums; // 存储用户输入的整数数组int num; // 用户输入的单个整数// 提示用户输入以0结束cout Enter numbers for the list (0 to end): ;while (cin num num ! 0) {nums.push_back(num); // 将输入的数字添加到数组中}// 创建链表ListNode* head createList(nums);// 打印交换前的链表cout Before reverse: ;printList(head);// 创建Solution类实例并交换Solution sol;ListNode* newHead sol.swapPairs(head);// 打印交换后的链表cout After reverse: ;printList(newHead);return 0; // 程序正常结束
}python
class Solution:def swapPairs(self, head: ListNode) - ListNode:dummy_head ListNode(nexthead)current dummy_head# 必须有cur的下一个和下下个才能交换否则说明已经交换结束了while current.next and current.next.next:temp current.next # 防止节点修改temp1 current.next.next.nextcurrent.next current.next.nextcurrent.next.next temptemp.next temp1current current.next.nextreturn dummy_head.next
