保安公司网站如何做,企业老板培训课程,微营销app,建筑人才网987孜孜不倦#xff1a;孜孜#xff1a;勤勉#xff0c;不懈怠。指工作或学习勤奋不知疲倦。#x1f493;#x1f493;#x1f493; 目录
说在前面
题目一#xff1a;返回倒数第k个节点
题目二#xff1a;链表的回文结构
题目三#xff1a;相交链表
SUMUP结尾 说在前… 孜孜不倦孜孜勤勉不懈怠。指工作或学习勤奋不知疲倦。 目录
说在前面
题目一返回倒数第k个节点
题目二链表的回文结构
题目三相交链表
SUMUP结尾 说在前面 dear朋友们大家好数据结构的学习离不开刷题在对链表的相关OJ进行练习后又更新复杂度的OJ这并不意味这链表的题目就结束了我们今天就继续联系链表相关的OJ练习。当今天我们的题目除了LeetCode还来自NowCoder。 友友们点击这里进入力扣leetcode学习 以下是leetcode题库界面 点击这里进入牛客网NowCoder刷题学习 以下是NowCoder题库界面
题目一返回倒数第k个节点
题目链接面试题 02.02. 返回倒数第 k 个节点 - 力扣LeetCode
题目描述
题目分析 思路1将创建一个数组temp将链表中节点的地址存入数组temp再返回数组中下标为n-k的地址所指向的数据。
举例1-2-3-4-5-6 和 k 3
代码如下 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
#define numsSize 100
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k) {ListNode* pcur head;ListNode* temp[numsSize];//创建临时数组int i 0;while (pcur ! NULL)//将链表节点地址存入数组temp{temp[i] pcur;pcur pcur-next;}return temp[i - k]-val;//返回倒数第k个节点的数据
} 不过假设链表很长此时空间复杂度就会比较高所以用numsSize固定长度显然不是好的办法应该用动态内存分配的办法来初始化temp
代码如下 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k) {ListNode* pcur head;int length 0;while (pcur ! NULL)//遍历数组得到节点的个数{length;pcur pcur-next;}//动态创建二级指针变量tempListNode** temp (ListNode**)malloc(length * sizeof(ListNode*));pcur head;int i 0;while (pcur ! NULL)//将链表节点地址存入temp{temp[i] pcur;pcur pcur-next;}return temp[i - k]-val;//返回倒数第k个节点的数据
} 不过显然空间复杂度为O(N)不是一个非常好的办法。如果给出前提条件空间复杂度为O(1)这个方法就不行了。 思路2将创快慢指针法定义快慢指针fast、slow先让fast走k步再让slow和fast同时走这样当fast走完slow刚好指向倒数第k个节点。
举例1-2-3-4-5-6 和 k 3
代码如下 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k) {//定义快慢指针ListNode* slow head;ListNode* fast head;while (k--)//让fast先走k步{fast fast-next;}//当fast走完此时slow指向的就是倒数第k个节点while (fast ! NULL){fast fast-next;slow slow-next;}return slow-val;
}
题目二链表的回文结构
题目链接链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
题目描述
题目分析 思路先找到链表的中间节点再将链表的后半部分反转比较前半部分和后半部分的元素是否相等。 我们需要用到之前OJ练习1中的两个函数 1.链表的中间节点876. 链表的中间结点 - 力扣LeetCode
2.反转链表206. 反转链表 - 力扣LeetCode
如果忘记了大家点击这里复习LeetCode/NowCoder-链表经典算法OJ练习1
代码如下
/*struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public://寻找链表的中间节点struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow head;struct ListNode* fast head;while (fast fast-next){slow slow-next;fast fast-next-next;}return slow;}//反转链表struct ListNode* reverseList(struct ListNode* head) {if (head NULL)return NULL;struct ListNode* n1 NULL;struct ListNode* n2 head;struct ListNode* n3 head-next;while (n2){n2-next n1;n1 n2;n2 n3;if (n3)n3 n3-next;}return n1;}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;}
};
像这种题属于组合体比较综合同时也告诉我们具有一定功能的代码在下次使用时可以稍加修改再CtrlC/V可以省去很多麻烦也比较方便。
题目三相交链表
题目链接160. 相交链表 - 力扣LeetCode
题目描述 题目分析
思路这题比较复杂我们需要模块化思考。同时注意单链表相交为Y型而不可能为X型因为单链表没有两个next指针。
1、如何判断相交
判断尾指针如果尾指针地址相同则相交注意不能用尾节点所存储的值是否相同判断因为之前有可能也有节点存储了和尾节点相同的值。
2、若相交如何找出第一个交点
思路1A链表的节点依次和B链表的所有节点比较A的某个节点和B链表的某个节点相等则这个节点就是交点。 代码如下
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {ListNode* cur1 headA;ListNode* cur2 headB;//让A、B链表都走到尾节点while(cur1-next){cur1 cur1-next;}while(cur2-next){cur2 cur2-next;}if(cur1 ! cur2)//判断尾节点是否相等return NULL;cur1 headA;while(cur1-next)//让A中每个节点都和B中的所有节点比较{cur2 headB;while(cur2-next){if(cur1 cur2)//第一个相等的就是交点return cur2;cur2 cur2-next;}cur1 cur1-next;} return cur2;
}
这个方法的时间复杂度为O(N^2)。
思路2分别计算出链表A、B的长度让长的先走差距的步数然后再让两链表同时开始走第一个相等的就是交点。 代码如下
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {ListNode* cur1 headA, * cur2 headB;int lenA 0;int lenB 0;while (cur1-next)//统计链表A的长度{lenA;cur1 cur1-next;}while (cur2-next)//统计链表B的长度{lenB;cur2 cur2-next;}if (cur1 ! cur2)//判断是否有交点return NULL;//假设法设置长短链表ListNode* LongList headA, * ShortList headB;if (lenA lenB){LongList headB;ShortList headA;}int gap abs(lenA - lenB);//两链表节点差值while (gap--)//让长的先走差值的步数{LongList LongList-next;}while (LongList ! ShortList)//让两链表一起走第一个相等的就是交点{LongList LongList-next;ShortList ShortList-next;}return LongList;
}
这个方法的时间复杂度为O(N)。
对比两种解法显然第二种方法是更好的。 SUMUP结尾 数据结构就像数学题需要刷题才能对它有感觉。之后还会更新数据结构相关的练习题、面试题希望大家一起学习共同进步~ 如果大家觉得有帮助麻烦大家点点赞如果有错误的地方也欢迎大家指出~
