网上做兼职的网站有哪些,官方网站建设 招标公告,中国投诉网站做袜子机器多少钱一台,国外wordpress主题站目录 第一题 思路#xff1a;
第二题 思路 第三题
描述
示例1 思路
总结#xff1a;这种类似的题#xff0c;都是用快慢指针#xff0c;相差一定的距离然后输出慢指针。 第一题 给你一个链表的头节点 head 和一个整数 val #xff0c;请你删除链表中所有满足 Node.val…目录 第一题 思路
第二题 思路 第三题
描述
示例1 思路
总结这种类似的题都是用快慢指针相差一定的距离然后输出慢指针。 第一题 给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 示例 1 输入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
输出[] 方法一
思路 快慢指针一个指向目标结点一个指向目标结点的前驱结点。用一个tmp保存pos-next. free()掉目标结点。 分两种情况如果只有一个节点或者要删除的结点是首元节点那么这时pre为NULLpos 指向pos否则pre-next pos struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* pre NULL;struct ListNode* pos head;while(pos!NULL){if(pos-valval){struct ListNode* tmp pos-next;free(pos);pos tmp;if(preNULL){head pos;}else{pre-next pos;}}else{pre pos;pos pos-next;}}return head;
}
方法二
思想 创建新链表用尾插法尾插法没有改变原指针的next指向所以不用保存next节点 但是在free时要保存下一节点。 struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur head;struct ListNode* newhead NULL;struct ListNode* tail NULL;while(cur!NULL){if(cur-val!val){if(newheadNULL){newhead tail cur;}else{tail-next cur;tail cur;}cur cur-next;}else{struct ListNode* tmp cur -next;free(cur);cur tmp;}}if(tail)tail-nextNULL;return newhead;} 第二题 给你单链表的头结点 head 请你找出并返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 示例 1 输入head [1,2,3,4,5]
输出[3,4,5]
解释链表只有一个中间结点值为 3 。示例 2 输入head [1,2,3,4,5,6]
输出[4,5,6]
解释该链表有两个中间结点值分别为 3 和 4 返回第二个结点。 思路 用快慢指针快指针一次走两个慢指针一次走一个。这样他们的路程之间差二倍。所以输出慢指针即输出中间节点。 struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow head;struct ListNode* fast head;while(fast!NULLfast-next!NULL){slow slow -next;fast fast-next-next;}return slow;
} 第三题 描述 输入一个链表输出该链表中倒数第k个结点。 示例1 输入 1,{1,2,3,4,5} 复制返回值 {5} 思路 用快慢指针快指针比慢指针先走k步然后两者在同时走。 struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {// write code herestruct ListNode* pre pListHead;struct ListNode* pos pListHead;while(k--){if(pos!NULL){pos pos-next;}else{return NULL;}}while(pos!NULL){pre pre-next;pos pos-next;}return pre;}
总结这种类似的题都是用快慢指针相差一定的距离然后输出慢指针。
第四题 给你单链表的头节点 head 请你反转链表并返回反转后的链表。 示例 1 输入head [1,2,3,4,5]
输出[5,4,3,2,1]示例 2 输入head [1,2]
输出[2,1]示例 3 输入head []
输出[]提示 链表中节点的数目范围是 [0, 5000]-5000 Node.val 5000 进阶链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题 方法一 将节点之间的next翻转。 用三个指针的原因是只用两个指针翻转时会导致链表断裂但是用第三个指针保存下一个节点这样链表就不会断裂。 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*///方法一
struct ListNode* reverseList(struct ListNode* head) {if(headNULL)return NULL;struct ListNode* left NULL;struct ListNode* right head;struct ListNode* tmp head-next;while(right!NULL){right-next left;left right;right tmp;if(tmp!NULL)tmp tmp-next;}return left;
}
方法二 用头插法注意头插法需要保存指针。尾插法不用保存指针。 错误总结 1注意头插是新结点指向头结点然后在将新节点设置为头结点。而不是直接将新节点设置为头节点
2C语言赋值语句左值是变量将新节点设置为头结点。newnode cur这是头结点为cur //方法二
struct ListNode* reverseList(struct ListNode* head)
{if(headNULL)return NULL;struct ListNode* cur head;struct ListNode* newhead NULL;while(cur!NULL){struct ListNode* next cur -next; //保存下一个cur-next newhead;newhead cur;cur next;}return newhead;
}
