简述如何优化网站的方法,如何重新运行wordpress,鄱阳网站建设,站群cms单链表OJ题#xff08;文字解读 图解#xff09; 1. 移除链表元素2. 反转链表3. 链表的中间结点4. 返回倒数第 k 个节点5. 合并两个有序链表 1. 移除链表元素
给你一个链表的头节点 head 和一个整数 val #xff0c;请你删除链表中所有满足 Node.val val 的节点#xff… 单链表OJ题文字解读 图解 1. 移除链表元素2. 反转链表3. 链表的中间结点4. 返回倒数第 k 个节点5. 合并两个有序链表 1. 移除链表元素
给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 OJ链接
struct ListNode* removeElements(struct ListNode* head, int val)这题当然可以暴力遍历将值一一对比相等的删除并重新链接。但还有更优的思路
定义两个指针(slow,fast);fast先走如果fast指向的val和其相等则让slow指向fast的下一个后fast再走如果不相等则让slow指向fast指向的位置后发射台再走最后再分一些特殊情况。
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* slow head;struct ListNode* fast head;//头为空直接返回空if(head NULL)return NULL;while(fast){if(fast-val val){slow-next fast-next;fast fast-next;}else{slowfast;fastfast-next;}} //当头结点就是val时并且头结点下一个结点为空直接返回空if(head-val valhead-nextNULL)return NULL;//当头结点就是val时并且头结点下一个结点不去为空直接返回头节点的下一个节点else if(head-val valhead-next!NULL)return head-next;else return head;
}最后一定要分情况不然OJ有些测试用例通过不了。
2. 反转链表
给你单链表的头节点 head 请你反转链表并返回反转后的链表。 OJ链接
struct ListNode* reverseList(struct ListNode* head)这题的最优解:
创建3个指针第一个指针n1指向空第二个指针n2指向头节点第三个指针n3指向头节点的下一个节点先将n2指向n1再让n1指向n2n2指向n3再循环往后走 struct ListNode* reverseList(struct ListNode* head) {struct ListNode* n1 NULL;struct ListNode* n2 head;while(n2){struct ListNode* n3 n2-next;n2-next n1;n1 n2;n2 n3;}return n1;
}最后一次当n3赋值给n2时n2指向空所以循环结束条件n2!NULL。如果将n3放在循环外创建可能会造成空指针因为数组可能只有一个元素或者就没有元素这样n3就没有用了。
3. 链表的中间结点
给你单链表的头结点 head 请你找出并返回链表的中间结点。
如果有两个中间结点则返回第二个中间结点。 OJ链接
struct ListNode* middleNode(struct ListNode* head) 这题还是快慢指针问题: 让一个指针从头节点开始一次走一步让第二个指针从头节点开始一次走两步走到尾时慢指针刚好走到中间节点。
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow head;struct ListNode* fast head;while(fast fast-next){fast fast-next-next;slow slow-next;}return slow;
}当节点个数为奇数个时循环终止条件为fast-next ! NULL当节点个数为偶时循环终止条件为fast ! NULL将两种情况合并。
4. 返回倒数第 k 个节点
实现一种算法找出单向链表中倒数第 k 个节点。返回该节点的值。 OJ链接
int kthToLast(struct ListNode* head, int k)这是一道经典的面试题最优思路为:先让一个指针从头节点走k步再让一个指针从头节点开始和前一个指针同时走当走到尾慢指针指向的就是我们要的。
int kthToLast(struct ListNode* head, int k){struct ListNode* slow head;struct ListNode* fast head;while(k--){fast fast-next;}while(fast){fast fast-next;slow slow-next;}return slow-val;
}循环结束条件为当fast NULL.
5. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 OJ链接
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2);解题思路 此题可以先创建一个空链表然后依次从两个有序链表中选取最小的进行尾插操作进行合并。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* head NULL,*tail NULL;//特殊情况先出if(list1 NULL){return list2;}if(list2 NULL){return list1;}while(list1 list2){if(list1-val list2-val){//第一次插入if(tail NULL){head tail list1;}else{//后续取较小的尾插tail-next list1;tail tail-next; }list1 list1-next;}else{if(tail NULL){head tail list2;}else{tail-next list2;tail tail-next; }list2 list2-next;}}//当list2走完list1还有节点时直接尾插if(list1){tail-next list1;}//当list1走完list2还有节点时直接尾插if(list2){tail-next list2;}return head;
}单链表没有这么简单目前程度我做不来难题后续有机会再更新.
