旅游推荐网站怎么做,做网站一年,怎么在百度首页做网站,做请柬的网站移除链表元素
题目链接#xff1a;力扣#xff08;LeetCode#xff09; 思路#xff1a;和前面学的单链表的中间删除数据一样#xff0c;使要被删除节点的前一个节点指向下要被删除节点的下一个节点#xff0c;然后把要被删除的节点free掉。 具体实现过程#xff1a;先…移除链表元素
题目链接力扣LeetCode 思路和前面学的单链表的中间删除数据一样使要被删除节点的前一个节点指向下要被删除节点的下一个节点然后把要被删除的节点free掉。 具体实现过程先定义prev和cur让cur指向头节点遍历链表如果cur-val!val让prev指向curcur指向cur的下一个节点prev始终在cur前面一个节点当cur-valval时停下让prev的下一个节点指向cur的下一个节点删除它们中间的cur节点然后让cur重新指向prve-next这就实现了节点的删除。但是还有一种情况如下图 头节点的数据等于val这时就需要判断了如果头节点数据等于val就要删除头节点然后把head重新指向原来的头结点的下一个节点cur重新指向head 代码如下
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode*prevNULL;struct ListNode*curhead;while(cur!NULL){if(cur-valval){if(prev){prev-nextcur-next;free(cur);curprev-next;}else{headcur-next;free(cur);curhead;}}else{prevcur;curcur-next;}}return head;
}
这道题还有一道解法就是重新开辟一个节点找到不相等的节点尾插到该节点的后面
直接上代码
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* newheadNULL;struct ListNode* curhead;struct ListNode* tailNULL;while(cur!NULL){if(cur-val!val){if(newhead NULL){tailnewheadcur;}else{tail-next cur;tail cur;}curcur-next;tail-nextNULL;}else{struct ListNode* next cur-next;free(cur);cur next;}}return newhead;
}
反转链表
题目链接力扣LeetCode 思路逆转链表中所有的箭头指向如下图所示 首先定义n1为null定义n2为原链表的头节点只要使n2下一个指向的是n1然后把n2给你n3给n2这样进行迭代直到链表的所有箭头全部反转就实现了反转链表注意在每次循环开始的时候都要用n3保存n2的下一个节点位置否则n2改变指向后就找不到后面的节点了。 代码如下代码中用rhead替代n1用cur替代n2用next替代n3
struct ListNode* reverseList(struct ListNode* head) {struct ListNode*curhead;struct ListNode*rheadNULL;while(cur){struct ListNode*nextcur-next;cur-nextrhead;rheadcur;curnext;}return rhead;
}
链表的中间节点
题目链接力扣LeetCode 思路定义快慢指针fast和slowfast每次走两步slow每次走一步如果有奇数个节点当fast走到最后一个节点时slow就走到中间节点了如果有偶数个节点当fast走到空slow就走到中间节点了。 因此我们在循环时要判断当fast和fast-next为空时就不能再继续了。 代码如下
struct ListNode* middleNode(struct ListNode* head) {struct ListNode*fasthead;struct ListNode*slowhead;while(fastfast-next){slowslow-next;fastfast-next-next;}return slow;
}
返回倒数第k个节点 题目链接力扣LeetCode 思路一 上文我们讲了如何反转链表这道题可以复用反转链表先把链表整体反转然后从前往后找第k个节点。 代码如下
int kthToLast(struct ListNode* head, int k){struct ListNode*curhead;struct ListNode*rheadNULL;while(cur){struct ListNode*nextcur-next;cur-nextrhead;rheadcur;curnext;}while(--k){rheadrhead-next;}return rhead-val;
} 思路二 定义快慢指针fast和slow先让fast走k步或者k-1步然后slow和fast一起走直到fast为空就停止如果先让fast走k-1步则当fast-next为空时停止这时slow节点就是要找的倒数第k个节点。 fast先走k步
int kthToLast(struct ListNode* head, int k){struct ListNode*fasthead;struct ListNode*slowhead;while(k--){fastfast-next;}while(fast){slowslow-next;fastfast-next;}return slow-val;
}
fast先走k-1步
int kthToLast(struct ListNode* head, int k){struct ListNode*fasthead;struct ListNode*slowhead;int nk-1;while(n--){fastfast-next;}while(fast-next){slowslow-next;fastfast-next;}return slow-val;
}
合并两个有序列表
题目链接力扣LeetCode 思路 创建一个新链表比较链表list1和list2中的值每次把较小的尾插在新节点的后面如果相等随便取其中一个尾插直到链表list1和list2中有一个被遍历完就停止循环。此时如果list1先结束list2中有剩余的节点直接把剩下的节点尾插到新链表后面同理如果list2先结束list1中有剩余就把list1中剩余的节点位插到新链表后面。注意如果list1开始就为空直接返回list2如果list2开始就为空直接返回list1。 代码如下
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode*newheadNULL;struct ListNode*tailnewhead;if(list1NULL)return list2;if(list2NULL)return list1;while(list1list2){if((list1-val)(list2-val)){if(tailNULL){tailnewheadlist1;}else{tail-nextlist1;tailtail-next;}list1list1-next;}else{if(tailNULL){tailnewheadlist2;}else{tail-nextlist2;tailtail-next;}list2list2-next;}}if(list1)tail-nextlist1;if(list2)tail-nextlist2;return newhead;
}
上述代码看起来很复杂因为在刚开始的时候不管是list1大还是list2大我们都要判断新链表的头结点是不是为NULL那如何能简化这个问题呢
这里我们来介绍一下哨兵位的头结点哨兵位的头结点不存储有效数据哨兵位的头结点相当于我们新开辟的一个节点可以直接在其后面尾插而不用担心它是不是NULL下图就是头结点和带哨兵位的头结点之间的区别 下面我们用哨兵位来实现一下上题
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode*newhead(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode*tailnewhead;if(list1NULL)return list2;if(list2NULL)return list1;while(list1list2){if((list1-val)(list2-val)){tail-nextlist1;tailtail-next;list1list1-next;}else{tail-nextlist2;tailtail-next;list2list2-next;}}struct ListNode*delnewhead;newheadnewhead-next;free(del);if(list1)tail-nextlist1;if(list2)tail-nextlist2;return newhead;
}
这就是哨兵位的优势了当我们用malloc开辟一个新节点newhead就可以直接在它后面尾插最后把newhead指向它的下一个节点然后释放newhead就行。哨兵位的使用让我们省略了很多判断过程。
分割链表
题目链接力扣LeetCode 思路我们可以使用哨兵位的头节点分别开辟一个“大链表”和“小链表”的头结点把原链表中的比x小的尾插到小链表的头结点之后把比x大的尾插到大链表的头结点之后遍历完原链表把大链表整体尾插到小链表后面具体如下图 注意最后要将哨兵位头结点释放掉。 这道题比较复杂分很多种情况 1.链表为空 2.链表元素全大于x 3.链表元素全小于x 4.有大有小 代码如下
struct ListNode* partition(struct ListNode* head, int x){//链表为空if(headNULL) return NULL;//链表全小于xint l 0;struct ListNode* tmp head;while(tmp){if(tmp-valx){l 1;}tmp tmp-next;}if(l 0){return head;}tmp head;//链表全大于xint g 0;while(tmp){if(tmp-valx){g 1;}tmp tmp-next;}if(g 0){return head;}struct ListNode*lesshead,*lesstail,*greaterhead,*greatertail;lessheadlesstail(struct ListNode*)malloc(sizeof(struct ListNode));greaterheadgreatertail(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* curhead;while(cur){if(cur-valx){lesstail-nextcur;lesstaillesstail-next;}else{greatertail-nextcur;greatertailgreatertail-next;}curcur-next;}lesstail-nextgreaterhead-next;greatertail-nextNULL;headlesshead-next;free(lesshead);free(greaterhead);return head;
}
链表的回文结构
题目链接链表的回文结构_牛客题霸_牛客网 思路这道题可以根据上面的题目代码来实现先找到中间节点然后把中间节点往后的链表反转使用双指针指针1从头节点开始指针2从中间节点开始比较它们的值如果相等分别往后移一位直到指针2指向空说明就是回文结构如果不相等说明不是回文结构。 代码如下
class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head) {struct ListNode*fasthead;struct ListNode*slowhead;while(fastfast-next){slowslow-next;fastfast-next-next;}return slow;
}struct ListNode* reverseList(struct ListNode* head) {struct ListNode*curhead;struct ListNode*rheadNULL;while(cur){struct ListNode*nextcur-next;cur-nextrhead;rheadcur;curnext;}return rhead;
}bool chkPalindrome(ListNode* phead) {struct ListNode*midmiddleNode(phead);struct ListNode*rmidreverseList(mid);while(rmid){if(phead-valrmid-val){pheadphead-next;rmidrmid-next;}else{return false;}}return true;}
}; 相交链表找两个链表的公共节点
题目链接力扣LeetCode 思路 首先先判断它们是不是相交链表只要判断它们的尾节点是不是相同的就行只要尾节点相同就必定相交因为相交链表只能是Y型的不可能是X型的下面就要返回相交链表的公共节点了可以计算一下两个链表的长度让长链表先走长度差步然后两个链表一起走如果有相同节点该节点就是公共节点如果没有说明两个链表没有公共节点。 代码如下
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode*tailAheadA;struct ListNode*tailBheadB;int lenA0;int lenB0;while(tailA-next){tailAtailA-next;lenA;}while(tailB-next){tailBtailB-next;lenB;}if(tailA!tailB){return NULL;}int gapabs(lenA-lenB);struct ListNode*longlistheadA;struct ListNode*shortlistheadB;if(lenAlenB){longlistheadB;shortlistheadA;}while(gap--){longlistlonglist-next;}while(longlist!shortlist){longlistlonglist-next;shortlistshortlist-next;}return longlist;
}
环形链表判断链表中是否有环
题目链接力扣LeetCode) 思路使用快慢指针快指针一次走两步慢指针一次走一步如果有环快指针先进环慢指针后进环快指针一定会某一时刻追上慢指针此时它们相等。如果没环快指针一定会最终指向空。 代码如下
bool hasCycle(struct ListNode *head) {struct ListNode*fasthead;struct ListNode*slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow)return true;}return false;
} 环形链表 II要求返回入环的第一个节点
题目链接力扣LeetCode 思路双指针法一个指针从头节点处开始走一个指针从相遇处的节点开始走当它们相等时就是入环节点。 推导过程 代码如下
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode*fasthead;struct ListNode*slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow){struct ListNode*meetfast;while(head!meet){headhead-next;meetmeet-next;}return meet;}}return NULL;
}
