企业网站建设工作室,上海原单外贸一条街,qq轻聊版,微网站和网站同步像素W...Y的主页 #x1f60a;
代码仓库分享 #x1f495; 前言#xff1a;
单链表的结构常常不完美#xff0c;没有双向链表那么”优秀“#xff0c;所以繁衍出很多OJ练习题。今天我们继续来look look数据结构习题。
下面就是OJ时间#xff01;#xff01;#xff01; …
W...Y的主页
代码仓库分享 前言
单链表的结构常常不完美没有双向链表那么”优秀“所以繁衍出很多OJ练习题。今天我们继续来look look数据结构习题。
下面就是OJ时间 【链表中倒数第K个节点】——牛客网 OJ链接 描述 输入一个链表输出该链表中倒数第k个结点。 示例1 输入 1,{1,2,3,4,5}返回值 {5} 题目函数接口 pListHead目标链表。k倒数第K个节点。 理论上我们可以先遍历一遍求出链表长度然后创建一个指针使其走过k-1个元素即可找到链表中倒是第k个节点。 但是这道题我们要把时间复杂度降到最大只能遍历一遍我们该怎么应对 我们可以创建两个指针(快慢)slow和fast将fast先走k个节点然后让fast与slow开始一块走直到fast指向NULL停止这时slow指向的节点就是我们需要倒数第k个节点 这里的快慢指针所使用的是路程差让fast先走k个就是让slow少走k个所得到的节点就是倒数第k个节点。 代码演示 struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* slow pListHead;struct ListNode* fast pListHead;while(k--){if(fast NULL)return NULL;fast fast-next;}while(fast){slow slow-next;fast fast-next;}return slow;
} 【leetcode 21.合并两个有序链表】 OJ链接 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 提示 两个链表的节点数目范围是 [0, 50]-100 Node.val 100l1 和 l2 均按 非递减顺序 排列 题目函数接口 list1目标链表1。list2目标链表2。 这道题与上篇博客中合并顺序表思路大同小异创建一个新节点取小的尾插到节点后面即可。 我们可以创建两个指针head与tailhead记录新链表的头节点tail记录新链表的尾节点。 代码演示 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode* cur list1;struct ListNode* tal list2;struct ListNode* head NULL;struct ListNode* tail NULL;if(list1 NULL)return list2;if(list2 NULL)return list1;while(tal cur){if(cur-valtal-val){if(head NULL){head tail list2;}else{tail-next tal;tail tail-next;}tal tal-next;}else{if(cur-valtal-val){if(head NULL){head tail list1;}else{tail-next cur;tail tail-next;}}cur cur-next;}}if(cur)tail-next cur;if(tal)tail-next tal;return head;
} 注意这种题我们就必须考虑完善比如一个链表为空我们就应该考虑这种情况应该直接返回另一个链表即可。 if(list1 NULL) return list2; if(list2 NULL) return list1; 这四句就是考虑为空的情况的所以我们做题必须全面 【CM11 链表分割】——牛客网 OJ链接 描述 现有一链表的头指针 ListNode* pHead给一定值x编写一段代码将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针。 题目函数接口 我们一看这个函数接口为c但是c与c在这个函数中内容相同所以使用c语言也是ok pHead目标链表。x分割数。 我们先举个实际例子说清楚题目含义【1 3 2 5 1】x 3 我们就应该以3为分界线将小于3的放在链表前面大于等于3的放在链表后面且顺序不能改变得到的顺序应该为【1 2 1 3 5】。 那我们该如何实现呢 我们可以创建两条链表将小于x的放入链表1大于等于x的放入链表2中然后进行合并即可得到结果。 大致思路已经出炉现在我们应该考虑一下细节该怎么处理。 两条链表我们应该选带哨兵位的还是不带哨兵位的 哨兵位是为了我们更好的头插一般情况下带不带哨兵位都可以不使用哨兵位可以使用二级指针进行操作效果是相同的。但是这道题是带哨兵位的链表简单些因为有特殊情况比如小于x的链表内容为空如果我们我们进行合并可能会丢失数据所以我们得用很多if语句进行判断才行但是有了哨兵位就不需要考虑这么多问题。 代码演示 class Partition {
public:ListNode* partition(ListNode* pHead, int x) {ListNode*ghead NULL;ListNode*gtail NULL;ListNode*lhead NULL;ListNode*ltail NULL;ghead gtail (ListNode*)malloc(sizeof(ListNode));lhead ltail (ListNode*)malloc(sizeof(ListNode));ListNode*cur pHead;while(cur){if(cur-val x){ltail-next cur;ltail ltail-next;}else{gtail-next cur;gtail gtail-next;}cur cur-next;}ltail-next ghead-next;gtail-next NULL;ListNode*head lhead-next;free(lhead);free(ghead);return head;}
}; 【OR36 链表的回文结构】——牛客网 OJ链接 描述 对于一个链表请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法判断其是否为回文结构。 给定一个链表的头指针A请返回一个bool值代表其是否为回文结构。保证链表长度小于等于900。 测试样例 1-2-2-1 返回true 题目函数接口 A目标链表。 那什么是回文呢 奇数回文1-2-3-2-1 偶数回文1-2-2-1 如果是数组可以从后往前进行非常简单但是这时链表应该怎么办呢 使用快慢指针找到链表的中间节点将中间节点后面的链表内容反转然后用两个指针一个在中间节点处一个在链表最开始出进行移动比较如果都相同则为回文结构反之则不是回文结构。 代码演示 class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head){struct ListNode* fast head;struct ListNode* slow head;while(fastfast-next){fast fast-next-next;slow slow-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;}bool chkPalindrome(ListNode* A) {struct ListNode* mid middleNode(A);struct ListNode* rmid reverseList(mid);while(rmid A){if(rmid-val ! A-val){return false;}rmid rmid-next;A A-next;}return true;}
}; 此程序我们封装了两个函数一个为寻找中间节点的函数一个为链表反转函数。当我们反转链表后我们不需要将中间节点的next重新连接让其成为相交链表即可。 这样判断的长度也一样不需要考虑何时停止。 【leetcode 160.相交链表】 OJ链接 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。 注意函数返回结果后链表必须 保持其原始结构 。 自定义评测 评测系统 的输入如下你设计的程序 不适用 此输入 intersectVal - 相交的起始节点的值。如果不存在相交节点这一值为 0listA - 第一个链表listB - 第二个链表skipA - 在 listA 中从头节点开始跳到交叉节点的节点数skipB - 在 listB 中从头节点开始跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点那么你的解决方案将被 视作正确答案 。 题目函数接口 headA目标链表A。headB目标链表B。 如何判断两个链表相交因为单链表一个结构体中只有一个next节点存放下一个结构体所以只需要判断尾节点地址是否相等即可。虽然我们找的不是最开始相交的点但是这样的思想非常简便。 首先按照前面思路判断两个链表是否相交如果不相交就没有做下去的必要了直接返回NULL即可。但是如果有节点我们就要寻找起始节点位置。 两个相交链表是由一段不相交的与一段相交的组合一起的两段链表不一样长的那一段一定在不相交的位置。所以我们可以让较长的链表先遍历两个链表长度之差个节点这样两个链表就一样长了再进行逐一比较即可找到起始相交节点 那我们想要知道两个链表长度就可以再判断两个链表是否相交时进行计数因为判断两个链表相交就是判断尾节点是否相等就是要将两个链表全部遍历一遍一举两得。 理论形成实践开始 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int lena 1;int lenb 1;struct ListNode *cura headA;struct ListNode *curb headB;while(cura-next){cura cura-next;lena;}while(curb-next){curb curb-next;lenb;}if(cura ! curb){return NULL;}int gap abs(lena-lenb);struct ListNode *llist headA;struct ListNode *slist headB;if(lena lenb){;}else{llist headB;slist headA;}while(gap--){llist llist-next;}while(llist ! slist){llist llist-next;slist slist-next;}return llist;
} 【leetcode 141.环形链表】 OJ链接 给你一个链表的头节点 head 判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 则返回 true 。 否则返回 false 。 题目函数接口 head目标链表。 什么是环形链表我们最先见到过的就是循环列表 但其实环形链表还有很多 向上面的我们都可以称作环形链表。 那我们应该怎样判断出链表为环形链表呢 这里我们还是基于快慢指针进行如同数学中的追及问题一样如果在一个环形跑到中两个人速度不同但是快的人落后于慢的人快的人总会追到慢的人。 我们创建两个指针fast与slows两个人都从开始进行slow走一步fast走两步如果有环它们一定会进入环中进行追及。 代码演示 bool hasCycle(struct ListNode *head) {struct ListNode *fast head;struct ListNode *slow head;while(fast fast-next){fast fast-next-next;slow slow-next;if(fast slow){return true;}}return false;
} 以上是本次数据结构OJ题分享感谢大家观看三连支持一下博主博主会干劲十足的
