湖南网站建设网,企业员工培训课程内容,合肥到黄山旅游攻略,东城网站建设公司#x1f495;人面只今何处去#xff0c;桃花依旧笑春风#x1f495; 作者#xff1a;Mylvzi 文章主要内容#xff1a;详解链表OJ题 题目一#xff1a;环形链表#xff08;判断链表是否带环#xff09;
题目描述#xff1a; 画图分析#xff1a;
代码实现#x… 人面只今何处去桃花依旧笑春风 作者Mylvzi 文章主要内容详解链表OJ题 题目一环形链表判断链表是否带环
题目描述 画图分析
代码实现 bool hasCycle(struct ListNode *head) {struct ListNode* slow head,*fast head;//定义快慢指针// 进入链表while(fast fast-next)//为空就不含有环{fast fast-next-next;slow slow-next;if(fast slow)//相等环存在return true;}return false;
} 题目二相交链表判断两个链表是否相交
题目描述 画图分析 代码实现
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA headA,* curB headB;int lenA 1;int lenB 1;//根据尾结点判断是否相交// 判断尾结点是否相同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*longlist headA,*shortlist headB;if(lenA lenB){longlist headB;shortlist headA;}//先让长的链表走gap步while(gap--){longlist longlist-next;}while(longlist ! shortlist){longlist longlist-next;shortlist shortlist-next;}//出循环--走到公共结点return longlist;
} 题目三链表分割哨兵位使用
题目描述 画图分析 代码实现
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {//创建哨兵位和两个链表struct ListNode* lhead,* ltail;//存放比x小的struct ListNode* ghead,* gtail;//存放比x大的lhead ltail (struct ListNode*)malloc(sizeof(struct ListNode));ghead gtail (struct ListNode*)malloc(sizeof(struct ListNode));//循环遍历尾插struct ListNode* cur pHead;while(cur){if(cur-val x){ltail-next cur;ltail cur;}else {gtail-next cur;gtail cur;}cur cur-next;}//不置空有可能呈环导致死循环gtail-next NULL;ltail-next ghead-next;//链接两个链表struct ListNode* head lhead-next;free(lhead);free(ghead);lhead NULL;ghead NULL;return head;}
};
哨兵位总结 “哨兵位”是一种特殊的结点放在链表头结点之前可以理解为工具人就告诉你我是结点不是NULL,但其本身不存储任何数据为了方便对链表的链接而设置的 出现链表链接使用哨兵位更简单因为可以避免一种特殊的结点--NULL,这种情况在之前往往需要单独讨论if语句而哨兵位的设立是我们不需要单独对这种情况讨论 题目四链表的回文结构判断是否时回文链表
题目要求 画图分析 代码实现
class PalindromeList {
public://第二种写法--头插
struct ListNode* reverseList(struct ListNode* head){//设置新的头结点进行头插struct ListNode* newhead NULL;struct ListNode* cur head;//头插while(cur){struct ListNode* next cur-next;cur-next newhead;newhead cur;cur next;}return newhead;
}struct ListNode* middleNode(struct ListNode* head){struct ListNode*slow head,*fast head;//开始移动while(fast fast-next){fast fast-next-next;//一次移动两步slow slow-next;}return slow;
}bool chkPalindrome(ListNode* head) {struct ListNode* mid middleNode(head);//得到中间结点struct ListNode* rmid reverseList(head);// 逆置中间结点之后的链表while(rmid head){//不等于--不是回文链表if(rmid-val ! head-val)return false;rmid rmid-next;head head-next;}return true;}
};
总结头插和尾插的区别画图分析
