学校网站 asp,网站结构方面主要做哪些优化,id如何打开wordpress,网站建设多少钱一个平台总结leetcode75中链表的算法题解题思路。 上一篇#xff1a;力扣75——队列 以下代码大部分为本人所写#xff0c;少部分为官方示例代码。 力扣75——链表 1 删除链表的中间节点2 奇偶链表3 反转链表4 链表最大孪生和1-4 解题总结 1 删除链表的中间节点
题目#xff1a;
给…总结leetcode75中链表的算法题解题思路。 上一篇力扣75——队列 以下代码大部分为本人所写少部分为官方示例代码。 力扣75——链表 1 删除链表的中间节点2 奇偶链表3 反转链表4 链表最大孪生和1-4 解题总结 1 删除链表的中间节点
题目
给你一个链表的头节点 head 。删除 链表的 中间节点 并返回修改后的链表的头节点 head 。长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点下标从 0 开始其中 ⌊x⌋ 表示小于或等于 x 的最大整数。对于 n 1、2、3、4 和 5 的情况中间节点的下标分别是 0、1、1、2 和 2 。题解前后指针。前指针指向最后一个个节点时后指针指向了中间节点。
/*** 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* deleteMiddle(ListNode* head) {ListNode* beforep head-next, *afterp head, *prep nullptr;if (beforep nullptr) return nullptr;while (beforep!nullptr) {prep afterp;afterp afterp-next;if (beforep !nullptr){beforep beforep-next;}if (beforep ! nullptr){beforep beforep-next;}}cout afterp-val;prep-next afterp-next;return head;}};2 奇偶链表
题目
给定单链表的头节点 head 将所有索引为奇数的节点和索引为偶数的节点分别组合在一起然后返回重新排序的列表。第一个节点的索引被认为是 奇数 第二个节点的索引为 偶数 以此类推。请注意偶数组和奇数组内部的相对顺序应该与输入时保持一致。你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。题解双指针分别指向奇数节点和偶数节点然后再串起来。
/*** 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* oddEvenList(ListNode* head) {if (head nullptr || head-next nullptr) return head;ListNode *ehead head-next, *optr head, *eptr head-next;while (true) {if (eptr-next ! nullptr) {optr-next eptr-next;optr optr-next;}else {optr-next nullptr;break;}if (optr-next ! nullptr) {eptr-next optr-next;eptr eptr-next;}else {eptr-next nullptr;break;}}optr-next ehead;return head;}};3 反转链表
题目
给你单链表的头节点 head 请你反转链表并返回反转后的链表。
题解我的做法是用一个栈存起来然后再串起来。官方的方法是用两个指针分别指向当前节点的父节点和子节点然后遍历一遍一个一个改。
/*** 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* reverseList(ListNode* head) {stackListNode* st;while (head) {st.push(head);head head-next;}ListNode *tmp new ListNode(0);head tmp;while (!st.empty()) {tmp-next st.top();tmp tmp-next;st.pop();}tmp-next nullptr;return head-next;}};4 链表最大孪生和
题目
在一个大小为 n 且 n 为 偶数 的链表中对于 0 i (n / 2) - 1 的 i 第 i 个节点下标从 0 开始的孪生节点为第 (n-1-i) 个节点 。比方说n 4 那么节点 0 是节点 3 的孪生节点节点 1 是节点 2 的孪生节点。这是长度为 n 4 的链表中所有的孪生节点。
孪生和 定义为一个节点和它孪生节点两者值之和。给你一个长度为偶数的链表的头节点 head 请你返回链表的 最大孪生和 。题解先用前后指针找到中间节点然后反转链表的后半截再遍历逐一求和。
/*** 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:int pairSum(ListNode* head) {ListNode* slow head;ListNode* fast head-next;while (fast-next) {slow slow-next;fast fast-next-next;}// 反转链表ListNode* last slow-next;while (last-next) {ListNode* cur last-next;last-next cur-next;cur-next slow-next;slow-next cur;}int ans 0;ListNode* x head;ListNode* y slow-next;while (y) {ans max(ans, x-val y-val);x x-next;y y-next;}return ans;}
};
1-4 解题总结
得用指针来索引遍历。 常用方法前后指针。
