大连网站建设开源,门户网站cms系统,网站设计与开发实例,wordpress图像存储一#xff1a;移除链表元素 我们很容易就可以想到一个解决方案#xff1a;再创建一个链表#xff0c;把不是val的结点拿过来尾插。
这样确实可以但是#xff0c;我们每次尾插都需要遍历一遍整个链表#xff0c;这样时间复杂度就变成了O(n^2)#xff0c;
因此我们不妨设…
一移除链表元素 我们很容易就可以想到一个解决方案再创建一个链表把不是val的结点拿过来尾插。
这样确实可以但是我们每次尾插都需要遍历一遍整个链表这样时间复杂度就变成了O(n^2)
因此我们不妨设置一个tail尾结点来指向它的尾。
画图分析 这里面还有一个潜在的问题就是假如最后一个节点的数值val怎么办想一想。
完整代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {ListNode* newhead;ListNode* newtail;ListNode* pcur head;newheadnewtailNULL;while(pcur){if(pcur-val!val){if(newheadNULL){newheadnewtailpcur;}else{newtail-nextpcur;newtailpcur;}}pcurpcur-next;}if(newtail!NULLnewtail-next!NULL){newtail-nextNULL;}return newhead;
}
二反转链表 这一题有两种解法
解法一
直接反转指向比如原来二指向三现在让三指向2.
画图分析 经过分析我们写出了这样的代码 struct ListNode* reverseList(struct ListNode* head) { struct ListNode* pprev NULL; struct ListNode* pcur head; struct ListNode* pnext head-next; while(pcur) { pcur-nextpprev; pprevpcur; pcurpnext; pnextpnext-next; } return pprev; } 放在力扣上提交 遇到错误不要慌张我们看一下提示信息可以发现原来是对NULL解引用了所以在17行那要加上判断那么说到这了万一这个链表原来就是空呢因此在一开始也要对这种情况处理。
完整代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* pprev NULL;struct ListNode* pcur head;struct ListNode* pnext;if(head){pnext head-next;}while(pcur){pcur-nextpprev;pprevpcur;pcurpnext;if(pnext){pnextpnext-next;}}return pprev;
}
解法二
取原链表中元素头插到新链表的newhead中。
画图分析
完整代码
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* pcur head;struct ListNode* newhead NULL;struct ListNode* pnext;if(head){pnexthead-next;}while(pcur){pcur-next newhead;newhead pcur;pcur pnext;if(pnext){pnext pnext-next;}}return newhead;
}
三链表的倒数k个结点 我们确实可以先遍历一遍拿到链表长度然后就可以找到倒数k个结点了。但是如果只能这么做就没有拿出来的必要了qwq。
快慢指针法两个指针先让一个走k然后一起走等到k指向空具体看下面画图分析结束。
画图分析
完整代码
struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) {struct ListNode* slow;struct ListNode* fast;slowfastpHead;while(k--){if(fast){fastfast-next;}else {return NULL;}}while(fast){slowslow-next;fastfast-next;}return slow;
}
四链表的中间结点 这题同样也是快慢指针法,大体思路是让fast走两步slow走一步但是直觉告诉我们结点数的奇偶性会影响结束条件。
画图分析 完整代码
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow;struct ListNode* fast;fastslowhead;while(fastfast-next){slowslow-next;fastfast-next-next;}return slow;
}
五合并两个有序链表 思路依次比较链表中的结点然后插入小的结点
画图分析 完整代码
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* newhead;struct ListNode* newtail;newheadnewtailNULL;struct ListNode* pcur1list1;struct ListNode* pcur2list2;if(pcur1NULL)return pcur2;if(pcur2NULL)return pcur1;while(pcur1pcur2){if(pcur1-valpcur2-val){if(newheadNULL){ newheadnewtailpcur1;}else{newtail-nextpcur1;newtailpcur1;}pcur1pcur1-next;}else{if(newheadNULL){ newheadnewtailpcur2;}else{newtail-nextpcur2;newtailpcur2;}pcur2pcur2-next;}}if(pcur1!NULL){newtail-nextpcur1;}if(pcur2!NULL){newtail-nextpcur2;}return newhead;
}
优化
我们每次都要对新创建的头结点判断是否为空。
有没有一种方法可以不用判断呢设置一个哨兵位就可以了
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* pcur1list1;struct ListNode* pcur2list2;if(pcur1NULL)return pcur2;if(pcur2NULL)return pcur1;struct ListNode* head (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* tail head;while(pcur1pcur2){if(pcur1-valpcur2-val){tail-nextpcur1;tailpcur1;pcur1pcur1-next;}else{tail-nextpcur2;tailpcur2;pcur2pcur2-next;}}if(pcur1!NULL){tail-nextpcur1;}else{tail-nextpcur2;}struct ListNode* newheadhead-next;free(head);return newhead;
}六链表分割
这题没给图直接画图分析
画图分析 完整代码
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {ListNode* lesshead (ListNode*)malloc(sizeof(ListNode));ListNode* lesstaillesshead;ListNode* greaterhead(ListNode*)malloc(sizeof(ListNode));ListNode* greatertailgreaterhead;ListNode* pcurpHead;if(pcurNULL)return NULL;while(pcur){if(pcur-valx){lesstail-nextpcur;lesstailpcur;}else {greatertail-nextpcur;greatertailpcur;}pcurpcur-next;}lesstail-nextgreaterhead-next;greatertail-nextNULL;ListNode* newheadlesshead-next;free(lesshead);free(greaterhead);return newhead;}
};
七链表回文 首先这一题开一个900的数组也可以过但是他并不符合空间复杂度O(1)。
然后我们说一下这一题的思路先找中间结点然后逆置最后一一比较。
具体细节请看下
画图分析 完整代码
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
struct ListNode* middleNode(ListNode* A)
{ListNode* slow A;ListNode* fast A;while(fast fast-next){fastfast-next-next;slowslow-next;}return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* pprev NULL;struct ListNode* pcur head;struct ListNode* pnext;if(head){pnext head-next;}while(pcur){pcur-next pprev;pprev pcur;pcur pnext;if(pnext){pnext pnext-next;}}return pprev;
}
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {ListNode* mid middleNode(A);ListNode* rhead reverseList(mid);ListNode* curA A;ListNode* curR rhead;while(curA curR){if(curA-val ! curR-val){return false; }else{curAcurA-next;curRcurR-next;}}return true;}
};
八链表相交 思路遍历一遍求长度同时判断是否会相交长的走差值步然后一起走直到两指针相同
这一题不可以用逆置做想一想为什么
画图分析 完整代码 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA headA;struct ListNode* curB headB;int lenA 1; int lenB 1;while(curA-next){lenA;curAcurA-next;}while(curB-next){lenB;curBcurB-next;}if(curA!curB)return NULL;int gap abs(lenA-lenB);struct ListNode* longlist headA;struct ListNode* shortlist headB;if(lenA lenB){longlist headB;shortlist headA;}while(gap--){longlistlonglist-next;}while(longlist!shortlist){longlistlonglist-next;shortlistshortlist-next;}return longlist;
}
九环形链表1 思路快慢指针法slow走1步fast走2步。如果相遇则带环否则不带环
画图分析
完整代码
bool hasCycle(struct ListNode *head) {struct ListNode* slow head;struct ListNode* fast head;while(fast fast-next){fastfast-next-next;slowslow-next;if(fastslow)return true;}return false;
}
十环形链表2 这一题有点数学题的意思。还是先说思路还是先slow与fast走等到两指针相遇在再让一个指针从都走另一个指针从相遇位置走直到二者再次相遇即为如环点。
画图分析 完整代码
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slow head;struct ListNode* fast head;while(fast fast-next){fastfast-next-next;slowslow-next;if(slowfast){struct ListNode* cur head;struct ListNode* curC fast;while(cur!curC){curcur-next;curCcurC-next;}return cur;}}return NULL;
}
十一复杂随机链表的拷贝
这一次最难搞的是random指针。思路也不好想大家还是借鉴一下大佬的思路吧。
思路在每个节点后面插入一个一样的节点定义cur 和 next指针 cur-next-radomcur-radom-next然后迭代往后。最后解开插入的结点。
画图分析 完整代码 struct Node* copyRandomList(struct Node* head) {struct Node* cur head;//插入新节点while(cur){struct Node* newnode (struct Node* )malloc(sizeof(struct Node));newnode-val cur-val;newnode-next cur-next;cur-next newnode;cur newnode-next;}//处理randomcur head;while(cur){struct Node* newnode cur - next;if(cur-randomNULL){newnode-random NULL;}else{newnode-random cur-random-next;}cur newnode-next;}//取新节点尾插同时恢复原链表cur head;struct Node* newhead NULL;struct Node* newtail NULL;while(cur){struct Node* newnode cur-next;struct Node* next newnode-next;if(newheadNULL){newhead newtail cur-next;}else{newtail-next newnode;newtail newnode;}cur-next newnode-next;cur newnode-next;}return newhead;
}
完
