深圳大型网站建设,正规营销型网站定制,wordpress固定链接规则文件,大学生毕业设计网站目录 一#xff1a;前言 二#xff1a;简单题目
(1)移除链表元素 (2)反转链表 (3)找链表的中间结点 (4)输入一个链表#xff0c;输出该链表中倒数第k个结点 (5)合并两个有序链表 (6)相交链表 (7)判断链表是否带环 三#xff1a;较难题目
(1)链表分割
(2)判断链表是否为回…目录 一前言 二简单题目
(1)移除链表元素 (2)反转链表 (3)找链表的中间结点 (4)输入一个链表输出该链表中倒数第k个结点 (5)合并两个有序链表 (6)相交链表 (7)判断链表是否带环 三较难题目
(1)链表分割
(2)判断链表是否为回文结构 (3)找到成环链表的入环结点 (4)复制带随机指针的链表 一前言 这一部分链表的OJ的题目适用于已经掌握链表基础的同学。 如果有对链表基础功能实现有问题的同学可以看这里 https://blog.csdn.net/2301_76269963/article/details/129586021?spm1001.2014.3001.5501 二简单题目 (1)移除链表元素 链接https://leetcode.cn/problems/remove-linked-list-elements/description/ 题目要求 基础思路 【1】特殊情况链表为空直接返回NULL。 【2】使用一个cur指针遍历整个链表。 【3】涉及到释放结点要提前用next指针记录下一个位置。 【4】 用prev记录要删除的结点的前一个结点保证链表连通。 【5】如果要删除prev不变不用删除的话prevnextcur都要迭代。 【6】如果删除的是头结点头结点要进行迭代。 代码 struct ListNode* removeElements(struct ListNode* head, int val) {//如果链表为空直接返回NULL。if (head NULL){return head;}//当前结点struct ListNode* cur head;//记录下一个结点struct ListNode* next head-next;//记录原结点struct ListNode* prev head;while (cur){//如果找到要删除的结点if ((cur-val) val){//如果释放的是头结点if (cur head){free(cur);head next;cur next;}//释放的不是头结点else{free(cur);prev-next next;}}//没找到进行prev迭代else{prev cur;}//迭代要考虑next已经为空的情况cur next;if (next)next next-next;}//返回头结点return head;
}(2)反转链表 链接https://leetcode.cn/problems/reverse-linked-list/description/ 题目要求 基础思路 【1】建立一个新的头。 【2】将原链表中的元素一个个拿下来。 【3】用prev记录新链表前一个结点然后让新拿下来的结点指向prev。 图解 代码 struct listnode* reverselist(struct listnode* head){//一个个拿出来链接struct listnode* newnode head;//记录前一个指针struct listnode* prev NULL;while (head){//head指向后一个结点head head-next;//改变结点指向newnode-next prev;prev newnode;//newnode要作为新的头结点不能指空if (head)newnode head;}return newnode;
} (3)找链表的中间结点 链接https://leetcode.cn/problems/middle-of-the-linked-list/description/ 题目要求 基础思路 【1】设置一个慢指针slow和一个快指针fast。 【2】慢指针slow走一步快指针fast走两步。 【3】当fast为空或者fast-next避免对空指针解引用为空就结束循环。 图解 代码 struct ListNode* middleNode(struct ListNode* head){//慢指针struct ListNode* slow head;//快指针struct ListNode* fast head;while (fast){//如果是偶数个结点fast为最后一个时应该直接跳出if (fast-next NULL)break;fast fast-next-next;slow slow-next;}//返回慢结点return slow;
} (4)输入一个链表输出该链表中倒数第k个结点 链接https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId13tqId11167rp2ru/activity/ojqru/ta/coding-interviews/question-ranking 题目要求 基础思路 【1】考虑特殊情况链表为空返回空给的k值大于链表结点数返回空。 【2】还是利用快慢指针快指针先走k步然后快慢指针相同速度走直到快指针为空此时慢指针就是要求的结点。 代码 struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {//如果为空链表直接返回空 if (pListHead NULL)return NULL;struct ListNode* slow pListHead;struct ListNode* fast pListHead;//快指针先走k步for (int i 0; i k; i){if (fast NULL)return NULL;fast fast-next;}//慢指针会一直落后k个结点while (fast){fast fast-next;slow slow-next;}//返回慢指针return slow;
} (5)合并两个有序链表 链接https://leetcode.cn/problems/merge-two-sorted-lists/description/ 题目要求 基础思路 【1】考虑特殊情况其中一个链表为空返回另一个链表。 【2】设置一个新头newhead和新尾newtail。 【3】依次比较链表结点小的拿下来作为新尾。相同情况拿第一个链表 【4】其中一个链表走空结束循环将没走完的链表的剩余结点链接到新链表后面。 图解 代码 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{//设置一个新的头和新的尾struct ListNode* newhead NULL, * newtail NULL;//如果其中一个链表为空返回另一个链表if (list1 NULL)return list2;if (list2 NULL)return list1;//如果第一个链表的结点数据大于第二个链表结点数据//那第二个链表的头结点作为新头反之第一个链表头结点作为新头if (list1-val list2-val){newhead newtail list2;list2 list2-next;}else{newhead newtail list1;list1 list1-next;}//一直循环直到一边为空while (list1 list2){//如果第一个链表的结点数据小把这个结点接到新链表后面//然后进行迭代指向下一个结点if (list1-val list2-val){newtail-next list1;newtail list1;list1 list1-next;}//如果第二个链表的结点数据小把这个结点接到新链表后面//然后进行迭代指向下一个结点else{newtail-next list2;newtail list2;list2 list2-next;}}//将没走到的链表的后续结点链接到新链表后面if (list1)newtail-next list1;elsenewtail-next list2;//返回新链表头return newhead;
}(6)相交链表 链接https://leetcode.cn/problems/intersection-of-two-linked-lists/description/ 题目要求 • 这个题目最好想到的方法就是暴力求解将其中一个链表的每一个结点与另一个链表的每一个结点比较如果存储的地址相同说明下一个结点是相交结点这样就利用了双重循环时间复杂度到达了O(n^2),我运行的时候没通过下面我们介绍一种时间复杂度为On,思路相对简单的方法。 基础思路 【1】考虑特殊情况其中一个链表为空返回空。 【2】易知当两个非空链表相交时两个链表的尾结点一定是相交结点我们可以利用尾结点判断两者是否相交。 【3】在找尾结点的同时计算两个链表的步长计算距离差距gap让长链表先走gap步然后两个链表一起走直到找到地址相同的结点即交点。 图解 代码 struct listnode* getintersectionnode(struct listnode* heada, struct listnode* headb) {//计算长度int lengtha 1;int lengthb 1;//如果其中一个为空返回空if (heada null || headb null)return null;//找两个链表的尾结点并计算长度struct listnode* taila heada;struct listnode* tailb headb;while (taila-next){taila taila-next;lengtha;}while (tailb-next){tailb tailb-next;lengthb;}//判断相交if (taila ! tailb){return null;}//计算相差步长abs函数可以算两数的绝对值int gap abs(lengthb - lengtha);//设B链表长A链表短struct listnode* longlist headb;struct listnode* shortlist heada;//如果A链表长改变值if (lengtha lengthb){shortlist headb;longlist heada;}//长链表先走gap步while (gap--){longlist longlist-next;}//循环求两个链表交点while (longlist ! shortlist){longlist longlist-next;shortlist shortlist-next;}//返回交点return longlist;
} (7)判断链表是否带环 链接https://leetcode.cn/problems/linked-list-cycle/description/ 题目要求 •在讲述基础思路前我想先进行一个数学推导如果有一个环形赛道其中一个人A以速度2m/s跑一个人B以速度1m/s跑 ,请问A是否能追上B 很明显A一定会追上B就像链表成环一样两步走的一方一定会在环内部追上一步走的一方链表的环长一定是正整数。 图解 基础思路 【1】考虑特殊情况链表为空返回空。 【2】设置一个慢指针slow和快指针fast,慢走一步快走两步。 【3】如果fast或者fast-next为空,说明链表不成环。 【4】如果成环fast一定会追上slow追上了返回true。 图解 代码 bool hasCycle(struct ListNode* head)
{struct ListNode* slow head, * fast head;//如果链表为空返回falseif (head NULL)return false;while (fast-next){//慢指针走一步快走两步slow slow-next;fast fast-next-next;//如果走完直接为空返回falseif (fast NULL)return false;//如果fast追到slow,说明链表成环返回true。if (fast slow)return true;}//如果fast-next为空链表不成环返回false。return false;
}三较难题目
(1)链表分割 链接https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId8tqId11004rp2ru/activity/ojqru/ta/cracking-the-coding-interview/question-ranking 题目要求 基础思路 【1】设计一个cur指针遍历链表。 【2】将链表分割成两个链表数据小于x的结点合成一个链表简称小链表数据大于x的合成一个链表简称大链表。 【3】考虑特殊情况链表为空返回空分割处理后如果其中一个链表为空返回另一个链表。 【4】分割结束后小链表的尾要和大链表的头链接大链表的尾要指向空。 图解 代码 struct listnode* partition(struct listnode* head, int x)
{//如果给的链表为空我们直接返回空if (head NULL)return NULL;//用来遍历整个链表struct listnode* cur head;//小于x的链表struct listnode* lesshead NULL;struct listnode* lesstail NULL;//大于等于x的链表struct listnode* biggerhead NULL;struct listnode* biggertail NULL;//遍历整个链表while (cur){if (cur-val x){//小于x的链表的第一个结点的插入if (lesshead NULL){lesshead lesstail cur;}else{ //让原来的尾指向新尾lesstail-next cur;lesstail cur;}}else{//小于x的链表的第一个结点的插入if (biggerhead NULL){biggerhead biggertail cur;}else{//让原来的尾指向新尾biggertail-next cur;biggertail cur;}}//cur迭代cur cur-next;}//小链表的尾指向大链表头大链表尾指空。//如果其中一个链表为空不对其解引用if (lesstail ! NULL)lesstail-next biggerhead;if (biggertail ! NULL)biggertail-next NULL;//如果没有元素小于x,返回大的链表if (lesstail NULL)return biggerhead;//如果没有元素大于x,返回小的链表elsereturn lesshead;
} (2)判断链表是否为回文结构 链接https://leetcode.cn/problems/aMhZSa/ 题目要求 基础思路 【1】先找到中间的结点。前面有 【2】反转中间结点后的链表。前面有 【3】遍历两个链表依次比较有不同返回false。 【4】循环结束条件为两个链表任意一个走到空。 图解 代码 //判断链表是否为回文
//找中间结点
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow head;struct ListNode* fast head;while (fast){if (fast-next NULL)break;fast fast-next-next;slow slow-next;}return slow;
}
//进行反转
struct ListNode* reverseList(struct ListNode* phead)
{struct ListNode* newnode phead;//记录前一个指针struct ListNode* prev NULL;while (phead){//head指向后一个结点phead phead-next;//改变结点指向newnode-next prev;prev newnode;//newnode要作为新的头结点不能指空if (phead)newnode phead;}return newnode;
}
//判断是否为回文
bool isPalindrome(struct ListNode* head)
{//找中间struct ListNode* mid middleNode(head);//反转struct ListNode* rHead reverseList(mid);//前半段struct ListNode* cur1 head;//后半段struct ListNode* curA rHead;//一个个判断不同直接返回falsewhile (cur1 curA){if (cur1-val ! curA-val){return false;}else{//如果相同迭代cur1 cur1-next;curA curA-next;}}//全部相同返回true。return true;
} (3)找到成环链表的入环结点 链接https://leetcode.cn/problems/linked-list-cycle-ii/description/ 题目要求 题目的两种思路 1.相遇后断开 基础思路 【1】设计快慢指针快走两步慢走一步找到第一次相遇的结点简称meet。 【2】在这个结点处断开meet指向空meet原来的下一个结点作为新链表的头。 【3】题目就转换为了求两个链表的交点。 图解 代码 //第二解法断开找交点
struct ListNode* detectCycle(struct ListNode* head)
{struct ListNode* slow head, * fast head;while (fast fast-next){slow slow-next;fast fast-next-next;//相遇if (fast slow){struct ListNode* meet fast;//第二个链表的头struct ListNode* newhead fast-next;fast-next NULL;//找到交点struct ListNode* headTail head;struct ListNode* newheadTail newhead;//计算长度int len 0;int newLen 0;while (headTail){headTail headTail-next;len;}while (newheadTail){newheadTail newheadTail-next;newLen;}//计算长度差距int gap abs(newLen - len);struct ListNode* longList newhead;struct ListNode* shortList head;if (len newLen){longList head;shortList newhead;}//长链表先走gap步while (gap--){longList longList-next;}while (longList ! shortList){longList longList-next;shortList shortList-next;}//返回交点return longList;}}//走到空返回NULLreturn NULL;
}2.数学公式法更加简洁 基础思路 【1】先进行数学推导。 【2】将公式转换成代码。 推导 代码 //判断是否成环并且找到入环点
struct ListNode* detectCycle(struct ListNode* head)
{//判断是否有环struct ListNode* fast head, * slow head;while (fast fast-next){slow slow-next;fast fast-next-next;//相遇if (fast slow){//公式法struct ListNode* meet slow;while (head ! meet){head head-next;meet meet-next;}return meet;}}//没有成环返回空。return NULL;
} (4)复制带随机指针的链表 链接https://leetcode.cn/problems/copy-list-with-random-pointer/description/ 题目要求 基础思路 【1】考虑特殊情况链表为空返回空。 【2】我们可以依次复制链表中的结点并将它们放在原链表结点之后。 图解 ★★★链接之后我们可以发现一个非常神奇的规律那就是除了random指向NULL的情况其它新生成结点的random都是它前一个结点的random的next。 【3】根据规律复制random 【4】合成新链表恢复原链表。 图解 代码 struct node* copyrandomlist(struct node* head)
{//如果链表为空。返回空if (head NULL)return NULL;//复制加链接struct node* cur head;while (cur){//生成新结点struct node* copy (struct node*)malloc(sizeof(struct node));//复制数据域copy-val cur-val;//复制指针域copy-next cur-next;//链接两个链表cur-next copy;//迭代cur copy-next;}//复制randomcur head;while (cur){struct node* copy cur-next;//cur-random为空的情况单独处理if (cur-random NULL)copy-random NULL;else{copy-random cur-random-next;}//迭代cur copy-next;}//切割复原cur head;//新链表的头和尾struct node* copyhead cur-next;struct node* copytail cur-next;while (cur ! NULL){//恢复原链表结构cur-next copytail-next;//cur迭代cur cur-next;//如果cur为空不进行迭代if (cur ){//旧尾指向新尾copytail-next cur-next;//迭代copytail copytail-next;}}//返回新链表的头return copyhead;
}
