网站的设计方案,基于云服务器的网站开发,微信公众号管理平台登录,wordpress菜鸟教程目录
1. 题目1#xff1a;返回倒数第k个节点
1.1 题目链接及描述
1.2 解题思路
1.3 程序
2. 题目2#xff1a;链表的回文结构
2.1 题目链接及描述
2.2 解题思路
2.3 程序 1. 题目1#xff1a;返回倒数第k个节点
1.1 题目链接及描述
题目链接#xff1a;
面试题 …目录
1. 题目1返回倒数第k个节点
1.1 题目链接及描述
1.2 解题思路
1.3 程序
2. 题目2链表的回文结构
2.1 题目链接及描述
2.2 解题思路
2.3 程序 1. 题目1返回倒数第k个节点
1.1 题目链接及描述
题目链接
面试题 02.02. 返回倒数第 k 个节点 - 力扣LeetCode
题目描述
实现一种算法找出单向链表中倒数第 k 个节点。返回该节点的值。
该题目已保证给定k保证有效
1.2 解题思路
思路1计数转换为正数
遍历单链表计数假设计得链表结点数为n倒数第k个元素即正数第n-k个元素再遍历返回第n-k个结点的值即可
时间复杂度O(N)但遍历链表两遍空间复杂度O(1)
思路2存储到数组中再下标访问正数元素
新创建一个数组遍历单链表依次将链表的结点值记录到数组中假设计得链表结点数为n结点值分别记录到数组下标0~n-1的位置返回下标为n-k的数组元素值即可
时间复杂度O(N)空间复杂度O(N)
思路3快慢指针本题解法
创建两个指针一个指针指向链表第一个结点称为慢指针一个指针指向链表第k个结点称为快指针
令两个指针同时向后遍历直至快指针指向空时此时慢指针即指向倒数第k个结点
时间复杂度O(N)只遍历链表一遍空间复杂度O(1)
1.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* fasthead,*slowhead;// 令fast先走k步while(k--){fastfast-next;}// 快慢同时走while(fast){slowslow-next;fastfast-next;}return slow-val;
}
2. 题目2链表的回文结构
2.1 题目链接及描述
题目链接链表的回文结构_牛客题霸_牛客网
题目描述
对于一个链表请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法判断其是否为回文结构。 给定一个链表的头指针A请返回一个bool值代表其是否为回文结构。保证链表长度小于等于900。
2.2 解题思路
思路1
存储到数组再创建两个计数变量分别从前向后和从后向前进行遍历来进行回文判断。
时间复杂度O(N)空间复杂度O(N)不符合要求
思路2本题解法
第一步定位链表的中间结点
第二步从中间结点开始将链表的后半段逆置
第三步创建两个指针一个指向链表第一个结点一个指向链表的中间结点两个同时向后走
对于偶数个结点的链表直至其中一个指针指向空即可对应匹配结束 对于奇数个结点的链表由于逆置的后半段链表并不影响原链表中间结点的的本来指向未逆置的前半段链表的最后一个结点的指向其实还是指向原链表的结点最终比较也是奇数个结点链表的中间结点的自我比较匹配结束标志仍是任意一个指针指向空 2.3 程序
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
using ListNode struct ListNode;
class PalindromeList {public:// 查找中间结点struct ListNode* middleNode(struct ListNode* head) {ListNode* slow head;ListNode* fast head;while (fast ! NULL fast-next ! NULL) {fast fast-next-next;slow slow-next;}return slow;}// 逆置链表struct ListNode* reverseList(struct ListNode* head) {// 判空if (head NULL) {return head;}// 创建三个指针ListNode* n1 NULL;ListNode* n2 head;ListNode* n3 n2-next;while (n2) {n2-next n1;n1 n2;n2 n3;if (n3)n3 n3-next;}return n1;}// 判断回文bool chkPalindrome(ListNode* A) {// 查找中间链表ListNode* midNodemiddleNode(A);// 逆置后半段链表ListNode* remidNodereverseList(midNode);while(remidNode A){if(remidNode-val ! A-val){return false;}remidNoderemidNode-next;AA-next;}return true;}
};
注关于查找单链表中间结点、逆置链表的实现在OJ相关文章有详解文章链接如下
【数据结构】_链表经典算法OJ力扣版-CSDN博客文章浏览阅读1.3k次点赞33次收藏21次。4、考虑特殊情况及相应处理1原链表为空即headNULL导致curNodeNULL不会进入第一个while循环但在newTail-nextNULL 时会导致空指针解引用操作出现错误。故需对newTail是否为空进行单独讨论处理。2新链表为空即原链表所有结点数据域的值都等于val导致newTail-nextNULL 时会导致空指针解引用操作出现错误。同1需对newTail是否为空进行单独讨论处理。处理逻辑为https://blog.csdn.net/m0_63299495/article/details/145355272https://blog.csdn.net/m0_63299495/article/details/145355272
