手机网站开发软件有哪些,知名网页设计师,住房和城乡建设厅门户网站,保健品网站模板移除链表元素#xff1a;
. - 力扣#xff08;LeetCode#xff09;
题目#xff1a;
给你一个链表的头节点 head 和一个整数 val #xff0c;请你删除链表中所有满足 Node.val val 的节点#xff0c;并返回 新的头节点 。
解题思路#xff1a; 情况1#xff1a; 情…
移除链表元素
. - 力扣LeetCode
题目
给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。
解题思路 情况1 情况2 情况3 我们以第一种情况写代码 ListNode* removeElements(ListNode* head, int val)
{ListNode* cur head;ListNode* slow head;while (cur){if (cur-val val){ListNode* tmp cur-next;free(cur);cur tmp;slow-next cur;}else{slow cur;cur cur-next;}}
}
以第二、三种特殊情况改代码
如果第一次就要删除头 struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur head;struct ListNode* tmp NULL;struct ListNode* slow head;while (cur){if (cur-val val){tmp cur-next;if(head-val val){free(cur);cur tmp;head cur;slow head;}else{free(cur);cur tmp;slow-next cur;}}else{slow cur;cur cur-next;}}return head;
}
反转链表
. - 力扣LeetCode
题目
给你单链表的头节点 head 请你反转链表并返回反转后的链表。 解题思路 考虑特殊
只有一个元素 同样适用 双指针解题一个前驱指针一个指向head的指针还有一个临时变量next为了记录head的next的值。
具体代码如下
ListNode* reverseList(ListNode* head)
{ListNode* cur head;ListNode* slow NULL;ListNode* next NULL;while (cur){next cur-next;cur-next slow;slow cur;cur next;}
}
链表的中间节点
. - 力扣LeetCode
题目 给你单链表的头结点 head 请你找出并返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。
解题思路 利用快慢指针有四种情况如图所示
第一种链表个数为偶数时 第二种链表个数为奇数时 第三种链表个数为1个时 第四种链表个数为2个时 综上 得出结论1、当链表个数大于2时且为偶数时 当快指针的next走到NULL时慢指针所在的地方就是中间结点的地方。 2、当链表个数大于2时且为奇数时 当快指针走到NULL时慢指针所在的地方就是中间节点的地方。 3、当链表个数等于1时 快指针和慢指针不需要走。 4、当链表个数为2时 和情况一是一样的。 综上 也就是快指针分两种情况 第一种就是快指针自身到达NULL时第二种就是快指针的next到达NULL时。 不论是那种情况最终都返回慢指针 代码如下
ListNode* middleNode(ListNode* head)
{ListNode* fast head;ListNode* slow head;while (fast){if (fast-next NULL){return slow;}fast fast-next-next;slow slow-next;}return slow;
}
合并两个有序链表
. - 力扣LeetCode
题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 解题思路 两个链表每个链表都有一个可以移动的指针接着让一个指针移动每移一步让两个指针指向的值做对比小的移下来然后让新链表的指针和刚刚移动过的俩把表指针往后走一步。 直到其中一个链表的指针指向空之后将另一个链表的剩下部分整体移过去 画图很重要
特殊考虑 如果其中一个链表为空可以指直接返回另一个链表的地址
代码如下
画图很重要
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* cur1 list1;struct ListNode* cur2 list2;struct ListNode* newhead NULL;struct ListNode* tmp NULL;if (cur1 NULL){return cur2;}else if(cur2 NULL){return cur1;}while (cur1 cur2){if (cur1-val cur2-val){if (newhead NULL){newhead tmp cur2;}else{tmp-next cur2;tmp tmp-next;}cur2 cur2-next;}else{if (newhead NULL){newhead tmp cur1;}else{tmp-next cur1;tmp tmp-next;}cur1 cur1-next;}}if (cur1 NULL){tmp-next cur2;}else{tmp-next cur1;}return newhead;
}
链表分割
链表分割_牛客题霸_牛客网
题目 现有一链表的头指针 ListNode* pHead给一定值x编写一段代码将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针。
解题思路 将比x大的和比x小的首先区分开最后再将其合并在一起
注意最后比x大的后面需要手动在末尾添加NULL指针 考虑特殊 如果链表中没有比x大的数或者没有比x小的数此时直接返回原链表的地址
代码如下
ListNode* partition(ListNode* pHead, int x)
{ListNode* cur pHead;ListNode* newhead1 NULL;ListNode* tmp1 NULL;ListNode* newhead2 NULL;ListNode* tmp2 NULL;while (cur){if (cur-val x){if (newhead1 NULL){newhead1 tmp1 cur;}else{tmp1-next cur;tmp1 tmp1-next;}}else{if (newhead2 NULL){newhead2 tmp2 cur;}else{tmp2-next cur;tmp2 tmp2-next;}}cur cur-next;}if (!(newhead1 newhead2)){return pHead;}tmp1-next NULL;tmp2-next newhead1;return newhead2;
}
链表的回文结构
链表的回文结构_牛客题霸_牛客网
题目
对于一个链表请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法判断其是否为回文结构。
给定一个链表的头指针A请返回一个bool值代表其是否为回文结构。保证链表长度小于等于900。 测试样例 1-2-2-1 返回true 解题思路 文字叙述 只需要将该链表进行反转后然后两个链表进行遍历如果中途有不一样的值就输出fasle 如果遍历结束后两个指针都指向NULL返回true就可以说明该链表是回文结构。 具体代码 ListNode* Reverse(ListNode*head)//链表反转代码
{ListNode* cur head;ListNode* slow NULL;while (cur){ListNode* tmp cur-next;cur-next slow;slow cur;cur tmp;}return slow;
}bool chkPalindrome(ListNode* pHead) //判断回文代码{ListNode* cur pHead;ListNode* newhead NULL;newhead Reverse(cur);while (curnewhead){if(cur-val ! newhead-val){return false;}cur cur-next;newhead newhead-next;}return true;// write code here}
