做一个网站开发项目有哪些阶段,建筑设计方案网站,免费无限建站,苏州木渎做网站文章目录 #x1f95d;24. 两两交换链表中的节点#x1f951;题目#x1f33d;算法原理#x1f96c;代码实现 #x1f34e;143. 重排链表#x1f352;题目#x1f345;算法原理#x1f353;代码实现 #x1f95d;24. 两两交换链表中的节点
#x1f951;题目 题目链接… 文章目录 24. 两两交换链表中的节点题目算法原理代码实现 143. 重排链表题目算法原理代码实现 24. 两两交换链表中的节点
题目 题目链接24. 两两交换链表中的节点 给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。
示例 1 输入head [1,2,3,4]
输出[2,1,4,3]示例 2
输入head []
输出[]示例 3
输入head [1]
输出[1]提示
链表中节点的数目在范围 [0, 100] 内0 Node.val 100
算法原理
解法一迭代模拟
做链表相关的题目不要**吝啬空间**这里我们先建立一个虚拟头节点这样可以一视同仁第一个交换的和后面交换的。
每次交换会涉及到四个节点的修改即要交换的2个节点和它们前后的两个节点这里也不吝啬空间这就创建4个临时变量。 何时终止交换 当链表节点个数为偶数的时候cur为空的时候停止交换当链表节点个数为奇数的时候next为空的时候停止交换 解法二递归
从宏观的角度将递归看作一个黑盒相信它一定能完成任务我们的任务就是让它帮我们完成节点的两两交换 先交换后面的节点然后把前面的节点连接起来即可。
代码实现
迭代
/*** 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){if(head nullptr || head-next nullptr) return head;ListNode* newHead new ListNode(0);newHead-next head;ListNode* prev newHead;ListNode* cur prev-next;ListNode* next cur-next;ListNode* nnext next-next;while(cur next){//交换prev-next next;next-next cur;cur-next nnext;//修改指针prev cur;cur nnext;if(cur) next cur-next;if(next) nnext next-next; }prev newHead-next;delete newHead;return prev;}
};运行结果 递归
/*** 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){if(head nullptr || head-next nullptr) return head;auto tmp swapPairs(head-next-next);auto ret head-next;head-next-next head;head-next tmp;return ret;}
};143. 重排链表
题目 题目链接143. 重排链表 给定一个单链表 L 的头节点 head 单链表 L 表示为
L0 → L1 → … → Ln - 1 → Ln请将其重新排列后变为
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …不能只是单纯的改变节点内部的值而是需要实际的进行节点交换。
示例 1 输入head [1,2,3,4]
输出[1,4,2,3]示例 2 输入head [1,2,3,4,5]
输出[1,5,2,4,3]提示
链表的长度范围为 [1, 5 * 104]1 node.val 1000
算法原理
链表的题目一般就是模拟或者递归此题我们模拟。
这里重排可以看作找到链表的中间节点前面部分正常排列后面部分逆序一下然后将两个部分一个接一个插入新链表 这样就分三步
找到链表的中间节点快慢指针 leetcode – 876.链表的中间节点后面部分逆序合并链表 这题的知识点很综合一题抵三题 代码实现
/*** 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:void reorderList(ListNode* head){//找中间节点ListNode* slow head, *fast head;while(fast fast-next){slow slow-next;fast fast-next-next;}//从slow-next开始逆序ListNode* headMid new ListNode(0);ListNode* cur slow-next;slow-next nullptr;while(cur){ListNode* next cur-next;cur-next headMid-next;headMid-next cur;cur next;}//合并链表ListNode* ret new ListNode(0);ListNode* prev ret;ListNode*cur1 head, *cur2 headMid-next;while(cur1) //cur1的长度cur2的长度{prev-next cur1;cur1 cur1-next;prev prev-next;if(cur2){prev-next cur2;cur2 cur2-next;prev prev-next;}}delete ret;delete headMid;}
};运行结果
