小俊哥网站建设,网站备案的幕布是什么,广州网站建设公司推荐乐云seo,好用的网站开发软件#x1f63d;PREFACE#x1f381;欢迎各位→点赞#x1f44d; 收藏⭐ 评论#x1f4dd;#x1f4e2;系列专栏#xff1a;数据结构刷题集#x1f50a;本专栏涉及到题目是数据结构专栏的补充与应用#xff0c;只更新相关题目#xff0c;旨在帮助提高代码熟练度#x…PREFACE欢迎各位→点赞 收藏⭐ 评论系列专栏数据结构刷题集本专栏涉及到题目是数据结构专栏的补充与应用只更新相关题目旨在帮助提高代码熟练度种一棵树最好是十年前其次是现在移除链表元素题目链接https://leetcode.cn/problems/remove-linked-list-elements/description/struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* prevNULL,*curhead;while(cur){if(cur-valval){prev-nextcur-next;free(cur);curprev-next;}else{prevcur;curcur-next;}}return head;
}提交一下我们会发现执行出错。正确代码struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* prevNULL,*curhead;while(cur){if(cur-valval){if(curhead){//头删headcur-next;free(cur);curhead;}else{prev-nextcur-next;free(cur);curprev-next;} }else{prevcur;curcur-next;}}return head;
}链表的中间结点题目链接https://leetcode.cn/problems/middle-of-the-linked-list/description/正确代码//尺取法
struct ListNode* middleNode(struct ListNode* head){struct ListNode* slowhead,*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;}return slow;
}链表中倒数第k个结点题目链接https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId13tqId11167rp2ru/activity/ojqru/ta/coding-interviews/question-rankingstruct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* fastpListHead,*slowpListHead;while(k--){fastfast-next;}while(fast){slowslow-next;fastfast-next;}return slow;;
}结果代码运行不过正确代码struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* fastpListHead,*slowpListHead;while(k--){if(fastNULL)//防止越界{return NULL;}fastfast-next;}while(fast){slowslow-next;fastfast-next;}return slow;;
}反转链表题目链接https://leetcode.cn/problems/reverse-linked-list/description/法一画图迭代//画图迭代
struct ListNode* reverseList(struct ListNode* head){struct ListNode* prev,*cur,*next;prevNULL,curhead,nexthead-next;while(cur){//反转cur-nextprev;//迭代prevcur;curnext;nextnext-next;}return prev;
}这个只是最基本的逻辑一运行发现还是过不了//画图迭代
struct ListNode* reverseList(struct ListNode* head){struct ListNode* prev,*cur,*next;prevNULL,curhead,nexthead-next;while(cur){//反转cur-nextprev;//迭代prevcur;curnext;if(next)nextnext-next;}return prev;
}再次提交发现还是过不去正确代码1//画图迭代
struct ListNode* reverseList(struct ListNode* head){if(headNULL)return NULL;struct ListNode* prev,*cur,*next;prevNULL,curhead,nexthead-next;while(cur){//反转cur-nextprev;//迭代prevcur;curnext;if(next)nextnext-next;}return prev;
}法二头插为什么能想到头插呢因为头插的顺序与链表的顺序刚好相反。正确代码2//头插
struct ListNode* reverseList(struct ListNode* head){struct ListNode* curhead, *newheadNULL;while(cur){struct ListNode* nextcur-next;//头插cur-nextnewhead;newheadcur;curnext;}return newhead;
}合并两个有序链表题目链接https://leetcode.cn/problems/merge-two-sorted-lists/description/法一不带哨兵位头结点//不带哨兵位头结点
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode* cur1list1,*cur2list2;struct ListNode* headNULL,*tailNULL;while(cur1cur2){if(cur1-valcur2-val){if(headNULL){headtailcur1;}else{tail-nextcur1;tailtail-next;}cur1cur1-next;}else{if(headNULL){headtailcur2;}else{tail-nextcur2;tailtail-next;}cur2cur2-next;}}if(cur1){tail-nextcur1;}if(cur2){tail-nextcur2;}return head;
}正确代码1//不带哨兵位头结点
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){//如果链表为空返回另一个if(list1NULL){return list2;}if(list2NULL){return list1;}struct ListNode* cur1list1,*cur2list2;struct ListNode* headNULL,*tailNULL;while(cur1cur2){if(cur1-valcur2-val){if(headNULL){headtailcur1;}else{tail-nextcur1;tailtail-next;}cur1cur1-next;}else{if(headNULL){headtailcur2;}else{tail-nextcur2;tailtail-next;}cur2cur2-next;}}if(cur1){tail-nextcur1;}if(cur2){tail-nextcur2;}return head;
}法二带哨兵位头结点正确代码2//带哨兵位头结点
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode* cur1list1,*cur2list2;struct ListNode* guardNULL,*tailNULL;guardtail(struct ListNode*)malloc(sizeof(struct ListNode));tail-nextNULL;while(cur1cur2){if(cur1-valcur2-val){tail-nextcur1;tailtail-next;cur1cur1-next;}else{tail-nextcur2;tailtail-next;cur2cur2-next;}}if(cur1){tail-nextcur1;}if(cur2){tail-nextcur2;}struct ListNode* headguard-next;//防止内存泄漏free(guard);return head;
}链表分割题目链接https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId8tqId11004rp2ru/activity/ojqru/ta/cracking-the-coding-interview/question-rankingclass Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* lessguard,*lesstail,*greaterguard,*greatertail;lessguardlesstail(struct ListNode*)malloc(sizeof(struct ListNode));greaterguardgreatertail(struct ListNode*)malloc(sizeof(struct ListNode));lesstail-nextgreatertail-nextNULL;struct ListNode* curpHead;while(cur){if(cur-valx){lesstail-nextcur;lesstaillesstail-next;}else{greatertail-nextcur;greatertailgreatertail-next;}curcur-next;}lesstail-nextgreaterguard-next;pHeadlessguard-next;free(greaterguard);free(lessguard);return pHead;}
};运行一下由于牛客不提供用例错误我们可以转到力扣官网上查。当然了也可以把我们写的用例往代码带看看哪出错了。正确代码class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* lessguard,*lesstail,*greaterguard,*greatertail;lessguardlesstail(struct ListNode*)malloc(sizeof(struct ListNode));greaterguardgreatertail(struct ListNode*)malloc(sizeof(struct ListNode));lesstail-nextgreatertail-nextNULL;struct ListNode* curpHead;while(cur){if(cur-valx){lesstail-nextcur;lesstaillesstail-next;}else{greatertail-nextcur;greatertailgreatertail-next;}curcur-next;}lesstail-nextgreaterguard-next;greatertail-nextNULL;//不能忽略pHeadlessguard-next;free(greaterguard);free(lessguard);return pHead;}
};链表的回文结构题目链接https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId49tqId29370rp1ru/activity/ojqru/ta/2016test/question-ranking正确代码//找中间节点
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow head, *fast head;while (fast fast-next) {slow slow-next;fast fast-next-next;}return slow;
}
//反转
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur head;struct ListNode* newhead NULL;while (cur) {struct ListNode* next cur-next;//头插cur-next newhead;//迭代newhead cur;cur next;}return newhead;
}class PalindromeList {public:bool chkPalindrome(ListNode* A) {struct ListNode* midmiddleNode(A);struct ListNode* rHeadreverseList(mid);struct ListNode* curAA;struct ListNode* curRrHead;while(curAcurR){if(curA-val!curR-val){return false;}else{curAcurA-next;curRcurR-next;}}return true;}
};相交链表题目链接https://leetcode.cn/problems/intersection-of-two-linked-lists/description/正确代码struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* tailAheadA,*tailBheadB;int lenA0,lenB0;while(tailA){lenA;tailAtailA-next;}while(tailB){lenB;tailBtailB-next;}//不相交的情况,不写的话leetcode也不会判错if(tailA!tailB){return NULL;}int gapabs(lenA-lenB);struct ListNode* longListheadA,*shortListheadB;if(lenAlenB){longListheadB;shortListheadA;}while(gap--){longListlongList-next;}while(longList!shortList){longListlongList-next;shortListshortList-next;}return shortList;
}环形链表题目链接https://leetcode.cn/problems/linked-list-cycle/description/正确代码bool hasCycle(struct ListNode *head) {struct ListNode* slowhead,*fasthead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow){return true;}}return false;
}环形链表II题目链接https://leetcode.cn/problems/linked-list-cycle-ii/description/法一双指针正确代码1struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slowhead,*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){//相遇struct ListNode* meetNodeslow;//公式while(meetNode!head){meetNodemeetNode-next;headhead-next;}return head;}}return NULL;
}法二:转化成链表相交正确代码2struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* tailAheadA,*tailBheadB;int lenA0,lenB0;while(tailA){lenA;tailAtailA-next;}while(tailB){lenB;tailBtailB-next;}//不相交的情况,不写的话leetcode也不会判错if(tailA!tailB){return NULL;}int gapabs(lenA-lenB);struct ListNode* longListheadA,*shortListheadB;if(lenAlenB){longListheadB;shortListheadA;}while(gap--){longListlongList-next;}while(longList!shortList){longListlongList-next;shortListshortList-next;}return shortList;
}struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slowhead,*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){struct ListNode* meetNodeslow;struct ListNode* list1meetNode-next;struct ListNode* list2head;meetNode-nextNULL;return getIntersectionNode(list1,list2);}}return NULL;
}复制带随机指针的链表题目链接https://leetcode.cn/problems/copy-list-with-random-pointer/description/正确代码struct Node* copyRandomList(struct Node* head) {//1.拷贝结点插入原结点的后面struct Node* curhead;while(cur)//遍历整个链表{//插入struct Node* copy(struct Node*)malloc(sizeof(struct Node));copy-valcur-val;struct Node* nextcur-next;//cur copy nextcur-nextcopy;copy-nextnext;curnext;}//2.拷贝random结点curhead;while(cur){struct Node* copycur-next;if(cur-randomNULL){copy-randomNULL;}else{copy-randomcur-random-next;}curcur-next-next;}//3.拆组struct Node* copyHeadNULL,*copyTailNULL;curhead;while(cur){struct Node* copycur-next;struct Node* nextcopy-next;//copy尾插if(copyHeadNULL){copyHeadcopyTailcopy;}else{copyTail-nextcopy;copyTailcopyTail-next;}//恢复原链表cur-nextnext;curnext;}return copyHead;
}
