作者：一个喜欢猫咪的的程序员
专栏：《Leetcode》
喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
目录
CM11 链表分割
链表分割_牛客题霸_牛客网
【牛客题霸】收集各企业高频校招笔面试题目，配有官方题解，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力
https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70
题目：
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
示例：
本题没有示例
思路：
本题我们利用两个guard1、guard2带头的链表，将他们合成一个链表来完成。
我们开辟一个链表结构体struct ListNode大小的动态空间n1、n2，将其强制类型转换为结构体指针struct ListNode*来将题目给的链表分为两个小链表。
我们让n1和guard1指向同一块动态空间，n2和guard2也是同理。
我们利用一个cur来遍历原链表，如果val比x小就尾插到第一个链表n1中，负责尾插到第二个链表n2中。
我们需要额外考虑一种情况，当第二个链表的尾不是原链表的最后一个时，n2的next不为空会出现环装链表的问题，我们需要将n2.next=NULL。
时间复杂度：O（N） 空间复杂度：O（N）
代码实现：
class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here struct ListNode* guard1; struct ListNode* guard2; struct ListNode* cur=pHead; struct ListNode* n1; struct ListNode* n2; n1=guard1=(struct ListNode*)malloc(sizeof(struct ListNode)); n2=guard2=(struct ListNode*)malloc(sizeof(struct ListNode)); n2->next=n1->next=NULL; while(cur) { if(cur->val<x) { n1->next=cur; n1=n1->next; } else { n2->next=cur; n2=n2->next; } cur=cur->next; } n1->next=guard2->next; n2->next=NULL; pHead=guard1->next; free(guard1); free(guard2); return pHead; } };
OR36 链表的回文结构
链表的回文结构_牛客题霸_牛客网
【牛客题霸】收集各企业高频校招笔面试题目，配有官方题解，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力
https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa
题目：
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
示例:
思路：
本题要求我们必须在O（1）的空间复杂度，因此我们不能去开数组，将他们一个个存起来。
我们可以将链表的后半段逆置，然后再将中间节点与头结点的元素做比较，判断是否相等。
这里逆置和查找中间节点的函数可以看一下我的另外2篇博客：
时间复杂度：O（N） 空间复杂度：O（1）
代码实现：
class PalindromeList { public: struct ListNode* reverseList(struct ListNode* head){ if (head == NULL || head->next == NULL) { return head; } struct ListNode*newhead=reverseList(head->next); head->next->next=head; head->next=NULL; return newhead; } struct ListNode* middleNode(struct ListNode* head){ if(head->next==NULL) { return head; } struct ListNode*left=head; struct ListNode*right=head; struct ListNode*ans=head; while(right!=NULL&&right->next!=NULL) { left=left->next; right=right->next->next; } ans=left; return ans; } bool chkPalindrome(ListNode* A) { // write code here struct ListNode*mid=middleNode(A); struct ListNode*rhead=reverseList(mid); while(A&&rhead) { if(A->val!=rhead->val) return false; A=A->next; rhead=rhead->next; } return true; } };
