网站源码素材,网站运营策划书范文,网站建设旗舰品牌,怎么建立一个网站能够与讯飞云对话目录 1.给你一个链表的头节点 head 和一个整数 val #xff0c;请你删除链表中所有满足 Node.val val 的节点#xff0c;并返回 新的头节点 。
2.给定一个带有头结点 head 的非空单链表#xff0c;返回链表的中间结点。如果有两个中间结点#xff0c;则返回第二个中间结点…目录 1.给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。
2.给定一个带有头结点 head 的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。
3.变形题找到链表中倒数第k个节点
4.经典题将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
结语 个人主页大耳朵土土垚-CSDN博客
所属专栏数据结构学习笔记 1.给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。
示例 1 输入head [1,2,6,3,4,5,6], val 6
输出[1,2,3,4,5]
解题思路
创建指针遍历链表找到对应节点删除
创建两个指针变量cur和pre用来记录cur表示当前遍历的节点pre表示上一个节点如图所示 不要忘了有两种情况当第一个节点就是对应节点时需要将头指针head改变
如果忘记第一种情况就会发现以下示例 图中null就是指pre为空指针的情况
以下是完整代码实现 struct ListNode {int val;struct ListNode* next;
};
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* cur head;struct ListNode* pre NULL;while (cur){if (cur-val val)//找到val值相同的节点时{if (pre NULL)//如果是第一个节点也就是图中第②种{cur head-next;free(head);head cur;}else//其他情况{pre-next cur-next;free(cur);cur pre-next;}}else//不相同时{pre cur;cur cur-next;}}return head;
} 另外一种思路
遍历链表把不是val节点拿出来尾插这里就不细讲有兴趣的可以打在评论区或私信我哦~
代码如下
struct ListNode {int val;struct ListNode* next;};
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* cur head;struct ListNode* newhead NULL;struct ListNode* tail NULL;while (cur){if (cur-val ! val){if (newhead NULL){tail cur;newhead cur;}else{tail-next cur;tail tail-next;}cur cur-next;tail-next NULL;}else{struct ListNode* pos cur;cur cur-next;free(pos);}}return newhead;
} 2.给定一个带有头结点 head 的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。 解题思路
给fastslow两个指针fast走两步slow走一步 ,当fast走到尾时slow恰好走到中间。
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* fast head, *slow head;while(fast!NULLfast-next ! NULL){slow slow-next;fast fast-next-next;}return slow;
} 3.变形题找到链表中倒数第k个节点
解题思路
还是快慢指针只要fast与slow之间距离为k那么当fast走到终点时slow所在的节点就是倒数第k个节点 struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {// write code here
struct ListNode* fast pListHead,*slow pListHead;for(int i 0; i k; i)//先让fast走k步{if(fast NULL)//如果k大于链表长度记得要及时返回哦return NULL;fast fast-next;}
while(fast)
{fast fast-next;slow slow-next;
}
return slow;
}
先让fast走k步拉开距离然后fast与slow一起走当fast为空指针时slow即为倒数第k个节点 4.经典题将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 解题思路 取小的尾插
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(head NULL){head tail list1;}else{tail-next list1;tail tail-next;}list1 list1-next;}else{ if(head NULL){head tail list2;}else{tail-next list2;tail tail-next;}list2 list2-next;}}if(list1 NULL){tail-next list2;}else{tail-next list1;}return head;
} 要注意当有链表为空的情况以及取小结束后的情况 结语
链表尾插我们可以用一个tail指针来记录尾插后的节点尾插直接在tail节点后即可这样就不用每次尾插都循环遍历大大减少了时间复杂度 提高了运行效率。大家如果有什么问题或者想法欢迎打在评论区或私信我哦~
