电商企业网站建设的一般要素有哪些,网站开发需要的技术人员有什么软件,小程序api有哪些,图片制作视频软件目录
一、移除链表元素
二、链表的中间结点
三、链表中倒数第k个结点
四、反转链表
五、合并两个有序链表
六、分割链表 一、移除链表元素 题目描述#xff1a;力扣 法一#xff1a;直接循环依次判断 对于这个题目#xff0c;我们最容易想到的一种思路就是#xff0c…目录
一、移除链表元素
二、链表的中间结点
三、链表中倒数第k个结点
四、反转链表
五、合并两个有序链表
六、分割链表 一、移除链表元素 题目描述力扣 法一直接循环依次判断 对于这个题目我们最容易想到的一种思路就是直接遍历链表当链表的值是需要删除的时候直接删除即可然后改变连接关系即可 代码如下 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* curhead;struct ListNode* prevNULL;while(cur!NULL){if(cur-val!val){prevcur;curcur-next;}else {if(headcur){headcur-next;free(cur);curhead;}else{struct ListNode* nextcur-next;free(cur);prev-nextnext;curnext;}}}return head;
} 对于我们写的这个代码我们有以下几点需要注意 1.当头结点就是需要删除的时候那么prev是为空的所以我们需要特殊处理采用头删的思路即可。 2.这个函数传递的是一级指针而非二级指针原因是题目要求最后返回了头结点。所以可以不使用二级指针。 3.当代码出现问题而在力扣上无法肉眼观察出错误的时候我们就需要放到vs上进行调试那么就涉及到需要自己手搓一个链表的问题手搓的方法如下所示 int main()
{struct ListNode* n1 (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n2 (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n3 (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n4 (struct ListNode*)malloc(sizeof(struct ListNode));n1-val 1;n2-val 2;n3-val 3;n4-val 4;n1-next n2;n2-next n3;n3-next n4;n4-next NULL;
} 法二尾插法 这个方法的思路是这样的我们重新定义一个链表这个链表使用两个结点指针来控制一个是头节点newhead,另一个是尾结点tail。一开始让他们都为空即这个链表是空链表 然后我们在使用一个结点指针cur来遍历原来的链表如果此处的值不是val那就将这个结点尾插到新链表上。然后让尾结点向后走cur结点也向后走。注意当第一个结点插入的时候由于tail为空所以特殊处理直接赋值然后使cur向后走即可 如果某处的值确实是val那么就要设置一个新结点next去接收cur的下一个结点然后释放cur。然后让tail的下一个结点赋值为cur。注意这里还有一个特殊情况是当题目所给的链表全要被删除的时候由于tail为空所以无法让tail的下一个结点赋值为cur。这里我们直接使用一个if排除掉这种情况即可 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* newheadNULL;struct ListNode* tailNULL;struct ListNode* curhead;while(cur!NULL){if(cur-val!val){if(newheadNULL){newheadcur;tailcur;curcur-next;}else {tail-nextcur;tailcur;curcur-next;}}else {struct ListNode* nextcur-next;free(cur);curnext;if(tail!NULL)tail-nextcur;}}return newhead;
} 二、链表的中间结点 题目描述力扣 解一 对于这道题我们最容易想到的思路就是先遍历一遍得到链表的长度然后除2就能得到要到达中间结点的长度。然后再一次遍历就能解出 解二快慢指针 对于这道题还有一种比较好的方法就是一开始定义两个结点指针然后一个一次走一步另外一个一次走两步如此一来慢的那个指针恰好就是中间结点。具体代码如下 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* middleNode(struct ListNode* head){struct ListNode* fasthead;struct ListNode* slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;}return slow;
} 三、链表中倒数第k个结点 题目链接链表中倒数第k个结点_牛客题霸_牛客网 对于这道题目与第二题十分相似也是采用快慢指针的方式不过不同的是这里的快慢是距离的快慢而上一道题是速度的快慢。 这道题目的关键就是fast应该要先走k步然后两者再一起走当fast为空的时候返回慢指针即可 如果fast先走k-1步那么fast的下一个指针为空的时候返回慢指针 注意如果链表为空那么直接返回空即可如果k大于链表长度那么就直接返回空就可以这就意味着fast先走的时候每走一步都要判断一下此时fast是否为空 /*** struct ListNode {* int val;* struct ListNode *next;* };*//*** * param pListHead ListNode类 * param k int整型 * return ListNode类*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{if(pListHeadNULL){return NULL;}// write code herestruct ListNode* fast pListHead;struct ListNode* slow pListHead;while(k--){if(fast!NULL)fastfast-next;elsereturn NULL;}while(fast){fastfast-next;slowslow-next;}return slow;
} 四、反转链表 题目描述力扣 解一直接改变指向 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head){struct ListNode* prevNULL;struct ListNode* curhead;while(cur!NULL){struct ListNode* nextcur-next;cur-nextprev;prevcur;curnext;}return prev;
} 如上代码所示这是最容易想到的方法直接改变指向我们先定义三个指针prevcur和next然后使用循环依次改变指向即可 解二头插法 这个的思路跟前面的尾插法类似 我们可以定义一个新的链表newhead然后将原来链表的头一个一个取出来进行头插即可 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head){struct ListNode* newheadNULL;struct ListNode* curhead;while(cur!NULL){struct ListNode* nextcur-next;cur-nextnewhead;newheadcur;curnext;}return newhead;
} 五、合并两个有序链表 题目描述力扣 解一尾插法 这道题目也是比较适合尾插如果第一个链表的数据小于第二个链表的数据那么就尾插第一个然后cur向后移动反之也是一样的代码如下 /*** 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;}if(list2NULL){return list1;}struct ListNode* cur1list1;struct ListNode* cur2list2;struct ListNode* newheadNULL;struct ListNode* tailNULL;while(cur1cur2){if((cur1-val)(cur2-val)){if(newheadNULL){newheadtaillist1;cur1cur1-next;}else{tail-nextcur1;tailcur1;cur1cur1-next;}}else{if(newheadNULL){newheadtaillist2;cur2cur2-next;}else{tail-nextcur2;tailcur2;cur2cur2-next;}}}if(cur1NULL){tail-nextcur2;}else{tail-nextcur1;}return newhead;
} 解二哨兵位 我们可以先创建一个哨兵位然后利用这个哨兵位去修改解法一的代码。可以一定程度上优化代码 /*** 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;}if(list2NULL){return list1;}struct ListNode* cur1list1;struct ListNode* cur2list2;struct ListNode* guardNULL;struct ListNode* tailNULL;guardtail(struct ListNode*)malloc(sizeof(struct ListNode));tail-nextNULL;while(cur1cur2){if((cur1-val)(cur2-val)){tail-nextcur1;tailcur1;cur1cur1-next;}else{tail-nextcur2;tailcur2;cur2cur2-next;}}if(cur1NULL){tail-nextcur2;}else{tail-nextcur1;}struct ListNode* headguard-next;free(guard);guardNULL;return head;
} 六、分割链表 题目链接力扣 解一尾插法不带哨兵位 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* partition(struct ListNode* head, int x){struct ListNode* lessheadNULL;struct ListNode* lesstailNULL;struct ListNode* greaterheadNULL;struct ListNode* greatertailNULL;struct ListNode* curhead;while(cur!NULL){if(cur-valx){//尾插到较小的链表if(lessheadNULL){lessheadlesstailcur;curcur-next;}else{lesstail-nextcur;lesstailcur;curcur-next;}}else{if(greaterheadNULL){greaterheadgreatertailcur;curcur-next;}else{greatertail-nextcur;greatertailcur;curcur-next; }}}if(lessheadNULL){return greaterhead;}if(greaterheadNULL){return lesshead;}lesstail-nextgreaterhead;greatertail-nextNULL;return lesshead;
} 对于这道题依旧采取尾插法既然要使用尾插法那么势必需要构建两个新链表 题目要求是将所有小于x 的值全部放在前面且不改变顺序 那么可以使用一个链表去管理小于x 的值。同样由于是尾插需要使用头尾两个结点来管理 然后使用另外一个链表去管理大于等于x的值也需要使用头尾两个结点去管理 由于是尾插那么势必涉及到链表为空这里的链表为空状态比较复杂。如果采用哨兵位的话确实可以避免分情况讨论了。但是这里我们选择迎难而上不采用哨兵位的解法 既然不采用哨兵位了那么我们现在来分析这道题首先是定义四个结点指针然后我们去遍历原来的链表如果小于x尾插到较小链表这里要注意如果链表为空需要分情况讨论。 如果大于等于x尾插到较大链表这里也要注意如果链表为空也需要分情况讨论 当尾插全部完成以后。 我们还需要进行分情况讨论如果较小链表为空那么直接返回较大链表即可如果较大链表为空返回较小链表即可。 然后我们链接较小链表和较大链表最后要注意较大链表的尾部一定要置空否则由于尾插可能会导致出现环。代码如上所示 解二尾插法带哨兵位 前面我们已经知道了不带哨兵位的方法我们发现分情况讨论特别繁琐。对于尾插法如果使用哨兵位就可以直接无视掉所有的分情况讨论。而大体思路却不会变化太多下面是代码。 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* partition(struct ListNode* head, int x){struct ListNode* lessGuardNULL;struct ListNode* lesstailNULL;struct ListNode* greaterGuardNULL;struct ListNode* greatertailNULL;lessGuardlesstail(struct ListNode*)malloc(sizeof(struct ListNode));greaterGuardgreatertail(struct ListNode*)malloc(sizeof(struct ListNode));greatertail-nextNULL;lesstail-nextNULL;struct ListNode* curhead;while(cur!NULL){if(cur-valx){lesstail-nextcur;lesstailcur;curcur-next;}else{greatertail-nextcur;greatertailcur;curcur-next; }}lesstail-nextgreaterGuard-next;greatertail-nextNULL;headlessGuard-next;free(lessGuard);free(greaterGuard);lessGuardgreaterGuardNULL;return head;
} 这里我们有一点需要特别注意一定要让greatertail-next置为空否则会陷入死循环这也是使用哨兵位就需要做的一些细节一旦使用哨兵位一定要注意一些细节 本小节内容就到这里了欲知后事请看下节
如果对你有帮助的话一定要点赞加收藏哦
