竞价网站转化率为多少,wordpress是什么语言,做商城网站应该注意什么,十大软件管理系统目录
1.移除链表元素
思路#xff1a; 2.反转链表
思路#xff1a;
3.链表的中间结点
思路#xff1a; 4.链表中的倒数第K个结点 思路#xff1a; 5.合并两个有序链表 思路#xff1a; 6.链表分割
思路#xff1a;
7.链表的回文结构
思路#xff1a; 8.随机链表…
目录
1.移除链表元素
思路 2.反转链表
思路
3.链表的中间结点
思路 4.链表中的倒数第K个结点 思路 5.合并两个有序链表 思路 6.链表分割
思路
7.链表的回文结构
思路 8.随机链表的复制 思路 1.移除链表元素
203. 移除链表元素 - 力扣LeetCode 给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 思路 定义新链表的头结点和尾结点循环遍历原链表即可遇到复合的结点删除即可 最后将尾结点的next置空。 因为这里并没有使用哨兵位所以第一次插入的时候要特殊处理 struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* newnode NULL,*tail NULL;struct ListNode* cur head;while(cur){//if(cur-val ! val){//空尾插if(tail NULL){newnode tail cur;}else{tail-next cur;tail tail-next;}cur cur-next;}else{struct ListNode* tmp cur;cur cur-next;free(tmp);tmp NULL;}}if(tail)tail-next NULL;return newnode;
} 2.反转链表
206. 反转链表 - 力扣LeetCode 给你单链表的头节点 head 请你反转链表并返回反转后的链表。 思路 定义三指针当前位置上一个位置下一个位置 将结点next链接到上一个结点即可然后将下一个位置赋给当前指针 struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur head;struct ListNode* prev NULL;while(cur){struct ListNode* next cur-next;cur-next prev;prev cur;cur next;} return prev;
}
3.链表的中间结点 876. 链表的中间结点 - 力扣LeetCode 给你单链表的头结点 head 请你找出并返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 思路 使用快慢指针方式快指针走两步慢指针走一步可以发现当快指针为NULL 或者快指针的下一个为空的时候 slow是中间结点 struct ListNode* middleNode(struct ListNode* head) {struct ListNode* fast head;struct ListNode* slow head;while(fast fast-next){//快指针走两步慢指针走一步fast fast-next-next;slow slow-next;}return slow;
} 4.链表中的倒数第K个结点
链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com) 输入一个链表输出该链表中倒数第k个结点。 思路 一般链表问题使用最多的解决方式就是快慢指针这个题目和第三题相似很多 先让快指针走K步然后两指针同时走 注这里的快指针和慢指针一起走 是一步步走同时防止快指针走K步越界了 struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {//快慢指针struct ListNode* fast pListHead;struct ListNode* slow pListHead;//快指针先走k步while(k--){if(fast NULL)return NULL;fast fast-next;}//同时走while(fast){fast fast-next;slow slow-next;}return slow;
} 5.合并两个有序链表
21. 合并两个有序链表 - 力扣LeetCode 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 思路 合并两个链表按照大小顺序排列尾插小的结点 第一次将走完链表其中一条注意并没有定义哨兵位所以第一次插入特殊处理 第二次将没走完的链表直接尾插到新链表后即可 将小的结点尾插到新链表中 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* newnode NULL,*tail NULL;if(list1 NULL)return list2;if(list2 NULL)return list1;while(list1 list2){if(list1-val list2-val){if(newnode NULL){newnode tail list1;}else{tail-next list1;tail tail-next;}list1 list1-next;}//list2else{if(newnode NULL){newnode tail list2;}else{tail-next list2;tail tail-next;}list2 list2-next;}}if(list1)tail-next list1;if(list2)tail-next list2;return newnode;
} 6.链表分割
链表分割_牛客题霸_牛客网 (nowcoder.com) 现有一链表的头指针 ListNode* pHead给一定值x编写一段代码将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针。 思路 对于链表分割最好用带头哨兵位的链表来解决减化了两条链表的链接问题如果不用哨兵位要增加很多特殊处理判断 有了哨兵位在链接两条链表时直接链接即可尾部置NULL ListNode* partition(ListNode* phead, int x) {struct ListNode* cur phead;struct ListNode* list1,*tail1,*list2,*tail2;//哨兵位list1 tail1 (struct ListNode*)malloc(sizeof(struct ListNode));list2 tail2 (struct ListNode*)malloc(sizeof(struct ListNode));while(cur){if(cur-val x) //小于x{tail1-next cur;tail1 tail1-next;}else //大于等于x{tail2-next cur;tail2 tail2-next;}cur cur-next;}tail1-next list2-next; //链接两条链表tail2-next NULL; //尾部置NULLphead list1-next;free(list1);free(list2);return phead;}
7.链表的回文结构 链表的回文结构_牛客题霸_牛客网 (nowcoder.com) 对于一个链表请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法判断其是否为回文结构。 给定一个链表的头指针A请返回一个bool值代表其是否为回文结构。保证链表长度小于等于900。 思路 1.先用快慢指针找到中间结点 2.反转中间节点后的链表 3.是否为回文判断 bool chkPalindrome(ListNode* head) {//快慢指针找到中间节点struct ListNode* slow head,*fast head;while(fast fast-next){fast fast-next-next;slow slow-next;}//此刻slow 是中间节点//反转mid后的链表struct ListNode* mid slow; struct ListNode* cur mid;struct ListNode* newnode NULL;while(cur){struct ListNode* next cur-next;cur-next newnode;newnode cur;cur next;}//回文比较struct ListNode* phead head;while(phead newnode){if(phead-val ! newnode-val)return false;phead phead-next;newnode newnode-next;}return true;} 8.随机链表的复制
138. 随机链表的复制 - 力扣LeetCode 给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 思路 1.先复制一条没有random的新链表每个节点尾插到对应结点后面 2.添加random可以发现复制的结点的上一个结点的random就是该结点需要的random 3.将添加后的链表尾插到新链表中记得跳过原链表的结点 struct Node* copyRandomList(struct Node* head) {struct Node* cur head;while(cur){struct Node* newnode (struct Node*)malloc(sizeof(struct Node));newnode-val cur-val;newnode-next cur-next;cur-next newnode;cur cur-next-next;}//添加randomcur head;while(cur){struct Node* copy cur-next;//原链表 random为空情况if(cur-random NULL){copy-random NULL;}else{copy-random cur-random-next;}cur cur-next-next;}//尾插cur head;struct Node* newnode NULL,*tail NULL;while(cur){struct Node* copy cur-next;struct Node* next copy-next;;if(tail NULL){newnode tail copy;}else{tail-next copy;tail tail-next;}cur-next next;cur next;}return newnode;
}
