移动端网站建设费用,开源 购物网站,网站建设与网页设计的论文,湖南网站制作电话【Leedcode】数据结构中链表必备的面试题#xff08;第三期#xff09; 文章目录【Leedcode】数据结构中链表必备的面试题#xff08;第三期#xff09;一、第一题1.题目2.思路3.源代码二、第二题1.题目2.思路(1)第一种情况#xff1a;偶数个链表(2)第二种情况#xff1a…【Leedcode】数据结构中链表必备的面试题第三期 文章目录【Leedcode】数据结构中链表必备的面试题第三期一、第一题1.题目2.思路3.源代码二、第二题1.题目2.思路(1)第一种情况偶数个链表(2)第二种情况奇数个链表3.源代码(1)链表的中间结点的实现(2)反转链表的实现(3)链表比较函数的实现(4)整体源代码总结一、第一题
1.题目 CM11 链表分割 如下示例 现有一链表的头指针ListNode*pHead给一定值x
编写一段代码将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针。 2.思路
1.使用两个哨兵位的头结点lesshead和greathead把小于4的连接到lesshead后面大于4的链接到greathead后面 2.再把小于4的最后一个连接到大于4的第一个具体如下图 注意如下图 3.源代码 代码如下示例 struct ListNode {int val;struct ListNode *next;
};
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* lessHead, *lessTail, *greaterHead, *greaterTail;lessHead lessTail (struct ListNode*)malloc(sizeof(struct ListNode));greaterHead greaterTail (struct ListNode*)malloc(sizeof(struct ListNode));lessTail-next greaterTail-next NULL;struct ListNode* cur pHead;while (cur) {if (cur-val x) {lessTail-next cur;lessTail lessTail-next;}else {greaterTail-next cur;greaterTail greaterTail-next;}cur cur-next;}lessTail-next greaterHead-next;greaterTail-next NULL;struct ListNode* list lessHead-next;free(lessHead);free(greaterHead);return list;}
};二、第二题
1.题目 OR36 链表的回文结构 如下示例 对于一个链表请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法判断其是否为回文结构。给定一个链表的头指针A请返回一个bool值代表其是否为回文结构。保证链表长度小于等于900。 2.思路
(1)第一种情况偶数个链表 (2)第二种情况奇数个链表 3.源代码
(1)链表的中间结点的实现 链表的中间结点的实现 如下示例 struct ListNode
{int val;struct ListNode *next;
}
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow,*quick;slowquickhead;while(quick quick-next){slow slow-next;quick quick-next-next;}return slow;
}(2)反转链表的实现 反转链表的实现 如下示例 struct ListNode
{int val;struct ListNode *next;
};
struct ListNode* reverseList(struct ListNode* head)
{//第二种方法struct ListNode* newheadNULL;struct ListNode* curhead;while(cur){struct ListNode* nextcur-next;cur-nextnewhead;newheadcur;curnext;}return newhead;
}(3)链表比较函数的实现 代码如下示例 class PalindromeList {
public:bool chkPalindrome(ListNode* A) {struct ListNode* mid middleNode(A);struct ListNode* rHead reverseList(mid);struct ListNode* curAA;struct ListNode* curR rHead;while( curA curR){if(curA - val ! curR -val){return false;}else {curAcurA-next;curR curR- next;}}return true;}
};(4)整体源代码 代码如下示例 struct ListNode
{int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow,*quick;slowquickhead;while(quick quick-next){slow slow-next;quick quick-next-next;}return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{//第二种方法struct ListNode* newheadNULL;struct ListNode* curhead;while(cur){struct ListNode* nextcur-next;cur-nextnewhead;newheadcur;curnext;}return newhead;}
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {struct ListNode* mid middleNode(A);struct ListNode* rHead reverseList(mid);struct ListNode* curAA;struct ListNode* curR rHead;while( curA curR){if(curA - val ! curR -val){return false;}else {curAcurA-next;curR curR- next;}}return true;}
};总结
以上就是今天要讲的内容本文介绍数据结构中链表必备的面试题第三期 如果我的博客对你有所帮助记得三连支持一下感谢大家的支持
