岳阳建设企业网站,旅游网站的建设背景,建设网站人员名单,深圳餐饮设计公司排名1 删除链表中等于给定值 val 的所有节点
删除链表中等于给定值 val 的所有节点 给你一个链表的头节点head和一个整数val#xff0c;请你删除链表中所有满足Node.valval的节点#xff0c;并返回新的头节点 输入#xff1a;head [1,2,6,3,4,5,6], val 6 输出#xff1a;[…1 删除链表中等于给定值 val 的所有节点
删除链表中等于给定值 val 的所有节点 给你一个链表的头节点head和一个整数val请你删除链表中所有满足Node.valval的节点并返回新的头节点 输入head [1,2,6,3,4,5,6], val 6 输出[1,2,3,4,5] 示例 2 输入head [ ], val 1 输出[ ] 示例 3 输入head [7,7,7,7], val 7 输出[ ] 思路如下 见详细代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode*prevNULL;struct ListNode*curhead;while(cur){if(cur-valval){if(curhead){headcur-next;curhead;}// headcur-next;// curhead;else{prev-nextcur-next;curprev-next;}}else{prevcur;curcur-next;}// else// {// prev-nextcur-next;// curprev-next;// }}return head;
}上述注释掉的代码是我在写的时候犯的错误大家也可以试着自己写写看会不会和我犯同样的错误 如果有其他思路可以随意发表意见
2 给定一个带有头结点 head 的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点
给定一个带有头结点 head 的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点 给你单链表的头结点head 请你找出并返回链表的中间结点 如果有两个中间结点则返回第二个中间结点 输入head [1,2,3,4,5] 输出[3,4,5] 解释链表只有一个中间结点值为3 输入head [1,2,3,4,5,6] 输出[4,5,6] 解释该链表有两个中间结点值分别为3和4返回第二个结点 思路 大部分人呢第一个想到的就是先去遍历一遍链表计算出链表的长度—然后再次遍历一遍链表找到链表的的中间结点 但是如果是在面试的时候面试官让你只能遍历一次那你应该怎么处理呢 这里运用的是快慢指针的相对速度 这时候我们可以考虑用快慢指针来作答 fast走两步slow走一步刚好天时地利人和走到了中间结点的位置 详细代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head){struct ListNode*slowhead;struct ListNode*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;}return slow;
}3 输入一个链表输出该链表中倒数第k个结点
输入一个链表输出该链表中倒数第k个结点 描述 输入一个链表输出该链表中倒数第k个结点 示例1 输入1,{1,2,3,4,5} 返回值{5} 思路一致 这里运用的快慢指针的相对距离 解法一
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* curpListHead;int count0;//建立一个计数器if(pListHeadNULL)//如果链表为空则返回空指针{return NULL;}while(cur)//循环遍历链表求出链表的长度{curcur-next;count;}if(k0kcount)//对k值的合理性进行判断{int poscount-k;//求出循环的次数while(pos){pListHeadpListHead-next;pos--;}return pListHead;//找到就返回目标结点}return NULL;
}解法二
//计数法 时间复杂度0n 空间O1
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{// write code hereif(pListHead NULL || pListHead-next NULL)//若链表没有结点或只有一个结点时返回第二条件不必须{return pListHead;}int nodenums 0;//记录总结点数第一次遍历)int returnnums 0;//第二次遍历每经过一次结点前置1)用于排查K结点struct ListNode* cur pListHead;while(cur ! NULL)//计数遍历{nodenums;cur cur-next;}if(knodenums)//如果k总结点数则代表不存在这一结点返回空{return NULL;}struct ListNode* pwe pListHead;while(pwe ! NULL)//第二次遍历寻找倒数K点{returnnums;//每经过一个结点就1if(nodenums-returnnums k)//如果结点总数减去当前结点数小于K那么这个结点就是倒数K结点{break;}pwe pwe-next;}return pwe;
}4 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 输入l1 [1,2,4], l2 [1,3,4] 输出[1,1,2,3,4,4] 示例 2 输入l1 [ ], l2 [ ] 输出[ ] 示例 3 输入l1 [ ], l2 [0] 输出[0] 思路 本质上是结构体指针的地址和成员变量next的相互赋值这里也涉及到了链表的尾插直接套用就可以了前提是掌握好了链表的增删查改基本逻辑 代码演示
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1NULL){return list2;}else if(list2NULL){return list1;}//定义一个head和tail//head和tail最初都置为NULL//tailtail-next//尾部插入struct ListNode*headNULL;struct ListNode*tailNULL;while(list1list2){//取小的尾部插入if(list1-vallist2-val){if(tailNULL){headtaillist1;//tailtail-next;}else{tail-nextlist1;tailtail-next;}list1list1-next; }else{if(tailNULL){headtaillist2;}else{tail-nextlist2;tailtail-next;}list2list2-next; }}if(list1){tail-nextlist1;}else if(list2){tail-nextlist2;}return head;
}
