学校门户网站建设的优势,南宁做网站比较好的公司,推广软文发布平台,室内设计师证报名入口官网文章目录前言分割链表回文链表写在最后前言 本章的OJ练习相对前面的难度加大了#xff0c;但是换汤不换药#xff0c;还是围绕单链表的性质来出题的。我相信#xff0c;能够过了前面的OJ练习#xff0c;本章的OJ也是轻轻松松。 对于OJ练习(3)#xff1a;- 传送门 但是换汤不换药还是围绕单链表的性质来出题的。我相信能够过了前面的OJ练习本章的OJ也是轻轻松松。 对于OJ练习(3)- 传送门 - 着重需要理解的是相交链表那道题的双指针思路明白为什么可以这样这样为什么可行。后面遇到类似的题目我还会做么 我们每做一道题目都要深挖他的题目结构明白为什么可以这样做。我相信如果你这样去做了并且不断地练习到后面每遇到一个题目你都会有所印象并能够很快的指出解这道题的思路。
分割链表 题目链接- 传送门 - 。 题目描述现有一链表的头指针 ListNode* pHead给一定值x编写一段代码将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针。 这里的不能改变原来的数据顺序也就是比x小的节点放在其余节点之前时这些节点的顺序应该与没有放之前是一样的。 例如: 2 4 8 5 9 3 5 给定 x 8通过本题目的描述最终的答案应该为2 4 5 3 5 8 9 。
图解描述给定x 3
解题思路 根据题目的意思以及不能改变原来的数据顺序这一特性我们可以以一种反归并的思想来想这道题。 我们遍历原链表并创建两个新链表这里的新链表表示的是在原链表基础上通过某一条件新连接的一串节点第一个链表用来尾插小于x的节点第二个链表用来尾插大于等于x的节点最后再将第一个链表的尾与第二个链表的头相连接再返回连接后的整个链表的头便ok啦。整个解题思路大致是这样后面来谈谈其中的细节。 对于创建的两个新链表都需要哨兵位的头节点来维护什么是哨兵位的头节点呢我们可以把哨兵位的头节点当作真实头节点的前驱它是一个不在答案范围内的节点但它却可以有效的控制真实的链表。其里面的值可以是随机的它的next初始指向NULL直到有节点尾插它的next就指向这个节点,而这个节点就是新连接的链表的真实的头。当最后连接完成时我们想要返回这个链表应该返回哨兵位的next因为哨兵位的next才是有效的真实的头节点。 如果说不用哨兵位的头节点来维护也是可以的。不过这样会有很多不必要的处理。比如给的原链表是NULL,或者两个新链表连接完后其中有一个为空这些都有可能造成解题出问题因此需要额外的处理。所以为了减少这些麻烦用哨兵位的头节点来维护这两个新链表上述的这些情况都能够有效避之上手写代码就有深刻的体会。 有了上面的铺垫我们只需要按照题目要求依次在原链表取节点然后在对应哨兵位节点指向的链表中尾插最后将这两个链表连接即可。 下面是代码实现 这里没学过c也不用担心代码纯都是C语言写的。 class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// 创建两个哨兵位的头节点// nhead作为连接比x小的节点// rhead作为连接大于等于x的节点struct ListNode* nhead (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* rhead (struct ListNode*)malloc(sizeof(struct ListNode));// 操控连接的指针nhead-next NULL, rhead-next NULL;struct ListNode* cur pHead, * cur1 nhead, * cur2 rhead;// 遍历原链表while (cur){// 如果小于x就尾插到nheadif (cur-val x) {cur1-next cur;cur1 cur1-next;}else // 如果 x 就尾插到rhead{cur2-next cur;cur2 cur2-next;}cur cur-next;}// 两个带哨兵位头节点的链表的连接// 第一个的尾连接第二个的头cur1-next rhead-next;// 将第二个的尾置为NULLcur2-next NULL;// 保存连接好的整个链表的头节点哨兵位头节点的下一个struct ListNode* newhead nhead-next;// 分别释放创建的两个哨兵位头节点free(nhead);free(rhead);// 返回新链表的头return newhead;}
};回文链表 题目链接- 传送门 - 。 题目描述给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。 回文结构相信大家已不陌生类似于123211233216789876这样的数字都可称之为回文数。而回文链表也是一样它每个节点的值组成的数就是一个回文数例如下面这些链表 那么我们该如何判断一个链表是否为回文链表呢
解题思路一 我们可以在不破坏原链表的情况下另外创建一个链表通过遍历原链表依次将原链表上的节点复制尾插到新链表。 然后两个链表从头开始比较如果有一个节点的值不相等就返回false。两个链表都遍历结束并且最后遍历的指针都同时指向NULL此时返回true。
下面是代码实现
bool isPalindrome(struct ListNode* head){struct ListNode* rhead NULL;struct ListNode* cur head;// 尾插到新链表while (cur){if (rhead NULL){rhead (struct ListNode*)malloc(sizeof(struct ListNode));rhead-val cur-val;rhead-next NULL;}else {struct ListNode* newnode (struct ListNode*)malloc(sizeof(struct ListNode));newnode-val cur-val;newnode-next rhead;rhead newnode;}cur cur-next;}struct ListNode* cur1 head, * cur2 rhead;while (cur1 cur2){// 有不同直接返回falseif (cur1-val ! cur2-val) return false;cur1 cur1-next;cur2 cur2-next;}// 如果结束且同时指向NULL说明回文if (cur1 NULL cur2 NULL) return true;else return false;
}该思路可以说是暴力解法效率相对较低并且开了额外的空间如果限制不能开额外的空间呢
解题思路二 上一个思路创建了额外的空间而本思路将不创建新的空间。 首先找到链表的中间节点然后从这个中间节点开始将后面的节点逆转最后从链表的头节点和逆转后返回的节点分别开始遍历判断。 如下图解析 可以看到整个判断过程是一个循环如果rhead指向空就结束循环说明是回文链表如果在循环期间发现有不一样的值的节点就直接返回false。 对于 - 找中间节点 - 和 - 反转链表 - 在前面已经讲解过了在这里我们直接 ctrl c , ctrl v 就好。
下面是代码实现
// 寻找中间节点函数
struct ListNode* middleNode(struct ListNode* head){struct ListNode* fast head, * slow head;while (fast fast-next){fast fast-next-next;slow slow-next;}return slow;
}// 反转链表函数
struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur head;struct ListNode* prev NULL;while (cur){struct ListNode* tmp cur-next;cur-next prev;prev cur;cur tmp;}return prev;
}bool isPalindrome(struct ListNode* head){// 找中间节点struct ListNode* mid middleNode(head);// 从中间节点开始反转链表struct ListNode* rlist reverseList(mid);// 判断while (rlist){if (head-val ! rlist-val) return false;rlist rlist-next;head head-next;} return true;
}写在最后 对于单链表的题目练习最重要的是思路我们在数据结构阶段要养成画图的习惯因为它能帮助我们更好的理解。后续还会有单链表相关的题目练习。 感谢阅读本小白的博客错误的地方请严厉指出噢
