【数据结构与算法】顺序表和链表题解

一、 移除链表元素 博主名称键盘敲碎了雾霭 个人专栏: 《C语言》《数据结构》⛺️指尖敲代码雾霭皆可破文章目录一、 移除链表元素1.1 问题描述1.2 解题思想1.3 代码实现二、反转一个单链表2.1 问题描述2.2 解题思想2.3 代码实现三、链表的中间结点3.1 问题描述3.2 解题思想3.3 代码实现四、返回倒数第k个节点4.1 问题描述4.2 解题思想4.3 代码实现五、合并两个有序链表5.1 问题描述5.2 解题思想5.3 代码实现六、链表分割6.1 问题描述6.2 解题思想6.3 代码实现七、链表的回文结构7.1 问题描述7.2 解题思想7.3 代码实现八、相交链表8.1 问题描述8.2 解题思想8.3 代码实现九、环形链表9.1 问题描述9.2 解题思想9.3 代码实现十、环形链表210.1 问题描述10.2 解题思想10.3 代码实现1.1 问题描述给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。原题链接203.移除链表元素1.2 解题思想创建新链表遍历原链表1.3 代码实现structListNode*removeElements(structListNode*head,intval){structListNode*pheadNULL;structListNode*ptailNULL;structListNode*purhead;while(pur){if(pur-val!val){if(pheadNULL){pheadptailpur;}else{ptail-nextpur;ptailpur;}}purpur-next;}if(pheadNULL){returnNULL;}ptail-nextNULL;returnphead;}二、反转一个单链表2.1 问题描述给你单链表的头节点 head 请你反转链表并返回反转后的链表。原题链接206.反转链表2.2 解题思想建立三个指针依次遍历2.3 代码实现structListNode*reverseList(structListNode*head){if(headNULL){returnhead;}structListNode*l1NULL;structListNode*l2head;structListNode*l3l2-next;while(l2){l2-nextl1;l1l2;l2l3;if(l3!NULL)l3l3-next;}returnl1;}三、链表的中间结点3.1 问题描述给你单链表的头节点 head 请你反转链表并返回反转后的链表。原题链接876.链表的中间结点3.2 解题思想建立三个指针依次遍历3.3 代码实现structListNode*middleNode(structListNode*head){structListNode*slowhead;structListNode*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;}returnslow;}四、返回倒数第k个节点4.1 问题描述实现一种算法找出单向链表中倒数第 k 个节点。返回该节点的值。原题链接面试题02.02.返回倒数第k个节点4.2 解题思想建立快慢指针有原始距离4.3 代码实现intkthToLast(structListNode*head,intk){structListNode*slowhead;structListNode*fasthead;while(k--){fastfast-next;}while(fast){slowslow-next;fastfast-next;}returnslow-val;}五、合并两个有序链表5.1 问题描述将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。原题链接21.合并两个有序链表5.2 解题思想新建立一个链表遍历两个原链表5.3 代码实现structListNode*mergeTwoLists(structListNode*list1,structListNode*list2){if(list1NULL){returnlist2;}elseif(list2NULL){returnlist1;}structListNode*l1list1;structListNode*l2list2;structListNode*pheadNULL;structListNode*ptailNULL;pheadptailmalloc(sizeof(structListNode));while(l1l2){if(l1-vall2-val){ptail-nextl1;ptaill1;l1l1-next;}else{ptail-nextl2;ptaill2;l2l2-next;}}if(l1){ptail-nextl1;ptaill1;l1l1-next;}if(l2){ptail-nextl2;ptaill2;l2l2-next;}structListNode*nextphead-next;free(phead);pheadnext;returnphead;}六、链表分割6.1 问题描述现有一链表的头指针 ListNode* pHead给一定值x编写一段代码将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针原题链接:CM11 链表分割6.2 解题思想构建两个链表最后再合并起来6.3 代码实现class Partition{public:ListNode*partition(ListNode*pHead,intx){structListNode*purpHead;structListNode*phead1(structListNode*)malloc(sizeof(structListNode));structListNode*ptail1phead1;structListNode*phead2(structListNode*)malloc(sizeof(structListNode));structListNode*ptail2phead2;while(pur){if(pur-valx){ptail1-nextpur;ptail1pur;}else{ptail2-nextpur;ptail2pur;}purpur-next;}ptail2-nextNULL;ptail1-nextphead2-next;returnphead1-next;// write code here}};七、链表的回文结构7.1 问题描述对于一个链表请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法判断其是否为回文结构。给定一个链表的头指针A请返回一个bool值代表其是否为回文结构。保证链表长度小于等于900。原题链接OR36 链表的回文结构7.2 解题思想先找中间节点再反转链表然后两链表比较7.3 代码实现class PalindromeList{public:structListNode*CheckMid(structListNode*head){structListNode*slowhead;structListNode*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;}returnslow;}structListNode*Rverse(structListNode*head){structListNode*l1NULL;structListNode*l2head;structListNode*l3head-next;while(l2){l2-nextl1;l1l2;l2l3;l3l3-next;}returnl1;}boolchkPalindrome(ListNode*A){structListNode*purA;structListNode*midCheckMid(A);structListNode*pheadRverse((mid));while(purphead){if(phead-val!pur-val){returnfalse;}purpur-next;pheadphead-next;}returntrue;// write code here}};八、相交链表8.1 问题描述给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。原题链接160.相交链表8.2 解题思想利用快慢指针算出相差的距离快的先走从同一位置依次遍历8.3 代码实现structListNode*getIntersectionNode(structListNode*headA,structListNode*headB){structListNode*l1headA;structListNode*l2headB;intcount10;intcount20;while(l1-next){count1;l1l1-next;}while(l2-next){count2;l2l2-next;}if(l1!l2){returnNULL;}intdifabs(count2-count1);structListNode*longlistheadA;structListNode*shortlistheadB;if(count1count2){longlistheadB;shortlistheadA;}while(dif--){longlistlonglist-next;}while(longlist!shortlist){longlistlonglist-next;shortlistshortlist-next;}returnlonglist;}九、环形链表9.1 问题描述给你一个链表的头节点 head 判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 则返回 true 。 否则返回 false 。原题链接141.环形链表9.2 解题思想利用快慢指针必相遇9.3 代码实现boolhasCycle(structListNode*head){structListNode*slowhead;structListNode*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(fastslow){returntrue;}}returnfalse;}十、环形链表210.1 问题描述给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。原题链接142. 环形链表10.2 解题思想利用快慢指针找到相遇的节点从该节点到成环的起始节点与头节点到成环的起始节点距离相同会相遇10.3 代码实现structListNode*detectCycle(structListNode*head){structListNode*slowhead;structListNode*fasthead;structListNode*pheadhead;while(fastfast-next){slowslow-next;fastfast-next-next;if(fastslow){structListNode*meetfast;while(meet!phead){meetmeet-next;pheadphead-next;}returnmeet;}}returnNULL;}