网站建设需要哪些企业资料,公司企业logo,广告平面设计教程,wordpress插件汉化下载地址在《波奇学单链表》中我们提到单链表的两个特点单向性。头节点尾节点的特殊性导致分类讨论的情况。如何看单链表#xff1f;让我们简化成下图cur表示当前节点#xff0c;下图表示cur移动#xff0c;圆圈表示值用哨兵卫节点(新的头节点)和把尾节点看成NULL来把头尾节点一般化…在《波奇学单链表》中我们提到单链表的两个特点单向性。头节点尾节点的特殊性导致分类讨论的情况。如何看单链表让我们简化成下图cur表示当前节点下图表示cur移动圆圈表示值用哨兵卫节点(新的头节点)和把尾节点看成NULL来把头尾节点一般化。struct ListNode*guard_h(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode*curguard_h;//作为移动节点相当于有了头节点的前驱节点可以cur-nextcur-next-next;循环删除尾节点不用cur-nextNULL(cur是4的地址)直接cur-nextcur-next-next;简化代码但要注意释放开辟的空间避免内存泄露。快慢指针创建两个指针一快一慢。快慢指针找链表的中间节点leetcode 876.链表中间节点struct ListNode*fasthead,*slowhead;
int count0;
while(fast)
{fastfast-next;count;if(count%20){slowslow-next;}
}
return slow;//结束时fast为空slow为中间节点的右边节点变式求中间节点的左节点如1-2-3-4求2fast走的节点数总节点数fast和slow指针走的节点数如图。struct ListNode*fasthead,*slowhead;
int count0;
while(fast)
{fastfast-next;count;if(count%21count3){slowslow-next;}
}
return slow;//结束时fast为空slow为中间节点的左边节点反转链表leetcode反转单链表struct ListNode* reverseList(struct ListNode* head) {struct ListNode* newhead NULL;struct ListNode* cur head;while(cur){//next指针指向cur的下个节点struct ListNode* next cur-next;cur-next newhead;newhead cur;cur next;}合并有序链表leetcode合并有序链表思路不要试图在原链表中进行插入操作再开一个新的头节点把原来链表的值拿过来链接。用哨兵节点可以简化代码短的拼完后再把剩下的链接在一起就行。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode*cur(struct ListNode*)malloc(sizeof(struct ListNode));cur-nextNULL;cur-val0;struct ListNode*headcur;while(list1list2){if(list1-vallist2-val){head-nextlist2;list2list2-next;}else{head-nextlist1;list1list1-next;}headhead-next;}struct ListNode*list3(list1!NULL?list1:list2);while(list3){head-nextlist3;list3list3-next;headhead-next;}return cur-next;
}合并链表快慢指针以及链表逆序这三板斧掌握了就可以解决leetcode上大部分的链表题。示例链表排序思路快慢指针找中间节点再用中间节点不断分割分割到只有一个节点或空链表。一节点链表进行合并有序链表最后把新链表再进行合并有序直到所有链表都合并完成。总而言之最基础就是这三个。
